我发现大佬好像都是用拓扑排序写的（本菜鸡不会拓扑哭唧唧
说一下并查集的做法吧...
就是找两人右边的（辣鸡的那个人）那个是否比左边厉害，厉害的话就矛盾。
如果他俩没比较过就把厉害的并到辣鸡的。
（辣鸡的是厉害的上一级
1 #include<stdio.h>
2 #include<algorithm>
3 #include<string.h>
4 #include<map>
5 #include<iostream>
6 #include<string>
7 using namespace std;
8
9 const int maxn=1010;
10 int par[maxn];
11 char a[maxn],b[maxn];
12 map<string,int> p; //把人名转换成数字表示
13
14 int find(int x) //并查集板子
15 {
16 while(x!=par[x]) x=par[x];
17 return x;
18 }
19
20 void unionn(int a,int b)
21 {
22 int fa=find(a);
23 int fb=find(b);
24 if(fa!=fb) par[fa]=fb;
25 }
26
27 int main()
28 {
29 int t;
30 while(scanf("%d",&t)!=EOF){
31 for(int i=1;i<=1000;i++){
32 par[i]=i;
33 }
34 p.clear(); //初始化
35 int cnt=1; //从1开始标记
36 int flag=1,g=1; //flag整体是否有矛盾出现 g本次是否矛盾
37 while(t--){
38 string a,b;
39 cin>>a>>b;
40 if(!p[a]) p[a]=cnt++; //如果这个名字没出现就赋一个新的值
41 if(!p[b]) p[b]=cnt++;
42 int k=20; //不超过20条（再大也行反正20之前迟早会break的：)
43 while(k--){
44 int s=find(p[b]);
45 if(s==p[b]) break; //如果b的上一级的上一级是b自己 b还没被比较
46 if(s==p[a]) {g=0; break;} //b的上一级的上一级的上一级的....看是否是a 是的话矛盾标记
47 }
48 if(g) unionn(p[a],p[b]); //左边的是右边下一级
49 else cout<<a<<' '<<b<<endl,flag=0,g=1; //有矛盾出现 flag标记 g要初始化否则下一次可能会出错
50 }
51 if(flag) printf("0\n");
52 }
53 return 0;
54 }