Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 79802 Accepted Submission(s): 25127
一开始还以为要用拓扑排序判断成环，但是这是无向图，拓扑排序应用于有向图的成环的判断，无向图要用并查集，对于有路的点并为一个集，检查每次输入的是否有同一个祖先即可，如果有就是成环了
注意必须只能有一个树！也就是只有一个祖先，不然也是不符合题目要求的
#include<bits/stdc++.h> using namespace std; int s[100005],a,b,flag,root,vis[100005]; int findf(int x) { return x==s[x]?x:s[x]=findf(s[x]); } void hebing(int a,int b) { int fa=findf(a); int fb=findf(b); if(fa!=fb) { s[fa]=fb; } } int main() { for(int i=1;i<=100000;i++) { s[i]=i; vis[i]=0; } while(~scanf("%d%d",&a,&b)) { if(a==-1&&b==-1) { return 0; } else if(a+b==0) { for(int i=1;i<=100000;i++) { if(vis[i]==1&&s[i]==i) root++; //统计根节点数量 if(root>1) { flag=1; break; } } if(flag) { printf("No\n"); } else { printf("Yes\n"); } flag=0; root=0; for(int i=1;i<=100000;i++) { s[i]=i; vis[i]=0; } } else { vis[a]=1; vis[b]=1; int fa=findf(a); int fb=findf(b); if(fa==fb) { flag=1; } else hebing(a,b); } } }
原文：https://www.cnblogs.com/dyhaohaoxuexi/p/12558516.html