题目描述：
You run a web service with \(N\) users.
The \(i\)-th user with a current handle \(S_i\) wants to change it to \(T_i\).
Here, \(S_1,…,\) and \(S_N\) are pairwise distinct, and so are \(T_1,…,\) and \(T_N\).
Determine if there is an appropriate order to change their handles to fulfill all of their requests subject to the following conditions:
-
you change only one user's handle at a time;
-
you change each user's handle only once;
-
when changing the handle, the new handle should not be used by other users at that point.
-
\(1 \leq N \leq 10^5\)
-
\(S_i\) and \(T_i\) are strings of length between \(1\) and \(8\) (inclusive) consisting of lowercase English letters.
-
\(S_i \neq T_i\)
-
\(S_i\) are pairwise distinct.
-
\(T_i\) are pairwise distinct.
输入描述：
\(N\)
\(S_1 T_1\)
\(S_2 T_2\)
\(⋮\)
\(S_N T_N\)
输出描述：
Print \(Yes\) if they can change their handles to fulfill all of their requests subject to the conditions; print \(No\) otherwise.
样例1：
input:
2
b m
m d
output:
Yes
The \(1\)-st user with a current handle b wants to change it to m.
The \(2\)-nd user with a current handle m wants to change it to d.
First, you change the \(2\)-nd user's handle from m to d; then you change the \(1\)-st user's handle from b to m. This way, you can achieve the objective.
Note that you cannot change the \(1\)-st user's handle to m at first, because it is used by the \(2\)-nd user at that point.
样例2：
input:
3
a b
b c
c a
output:
No
The \(1\)-st user with a current handle a wants to change it to b.
The \(2\)-nd user with a current handle b wants to change it to c.
The \(3\)-rd user with a current handle c wants to change it to a.
We cannot change their handles subject to the conditions.
样例3：
input:
5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc
output:
Yes
AC代码1：
#include <bits/stdc++.h>
using namespace std;
// 输入的字符串是N的两倍，所以要开两倍，不然就RE了
const int N = 2e5 + 10;
int n;
vector<string> g(N), m(N);
unordered_map<string, int> q;
unordered_map<string, vector<string>> p;
// 根据题意，只要所给的输入不会形成一个环就可以
// 那么把所给的输入抽象成一个有向图，问题就转变为判断一个图是不是有向无环图
// 而一个有向无环图一定是一个拓扑序列，所以最终只需要判断是不是一个拓扑序列就好了
// 直接默写模板
bool topsort()
{
queue<string> s;
int cnt = 0;
// 将入度为0的字符串存入队列
for(auto j : q)
if(!j.second)
{
s.push(j.first);
cnt ++;
}
while(s.size())
{
auto t = s.front();
s.pop();
// 删除每个入度为0的字符串t和其他字符串v的边
// 如果删完之后 v 的入度也为0，则也存入队列
for(auto &v : p[t])
{
if(-- q[v] == 0)
{
s.push(v);
cnt ++;
}
}
}
// 如果整个过程结束后，每个点都存如果队列，则么就是拓扑序列
return cnt == q.size();
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++)
{
// 输入两个字符串
cin >> g[i] >> m[i];
// 判断每个字符串的入度
q[m[i]] ++;
q.insert({g[i], 0});
// 如果是整形可以用邻接表，但这里比较特殊就用map加vector来有向连接两个字符串
p[g[i]].push_back(m[i]);
}
if(topsort())
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
AC代码2：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
string s[N];
vector<string> g(N), m(N);
unordered_map<string, int> q;
unordered_map<string, vector<string>> p;
bool topsort()
{
// 思路与上一个代码一样的，不过这里用数组模拟队列
int hh = 0, tt = -1;
for(auto j : q)
if(!j.second)
s[++ tt] = j.first;
while(hh <= tt)
{
auto t = s[hh ++];
for(auto &v : p[t])
if(-- q[v] == 0)
s[++ tt] = v;
}
return tt == q.size() - 1;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> g[i] >> m[i];
q[m[i]] ++;
q.insert({g[i], 0});
p[g[i]].push_back(m[i]);
}
if(topsort())
cout << "Yes\n";
else
cout << "No\n";
return 0;
}