AtCoder Beginner Contest 285 ——D

题目：D - Change Usernames (atcoder.jp)

题解：在所有的s[i]和t[i]之间连接一条有向边，由s[i]指向t[i]，连接完之后可以发现，会形成若干条链或者环，如果出现了环那么一定不可以实现，所以用拓扑排序判断是否出现了环即可

代码：

#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef unsigned long long ULL;
const ll mod = 998244353;
const int N = 1e5 + 5;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
vector<string> s,t;
map<string,string> e;
map<string,int> in;
queue<string> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string ts,tt;
        cin>>ts>>tt;
        s.push_back(ts);
        t.push_back(tt);
        e[ts]=tt;
        in[ts];
        in[tt]=1;
    }
    int ans=0;
    for(auto x:in)
    {
        if(x.second==0)q.push(x.first),ans++;
    }
    while(q.size())
    {
        auto x=q.front();
        q.pop();
        if(e.find(x)!=e.end())
        {
            in[e[x]]--;
            if(in[e[x]]==0) q.push(e[x]),ans++;
        }
    }
    if(ans==in.size()) cout<<"Yes";
    else cout<<"No";
    return 0;
}