并查集的应用。
实质上是判断这是否是一棵树。
需要注意的是0 0 也是一棵树。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[100001],n; int vis[100001]; int fa(int x) { if(x!=a[x]) return a[x]=fa(a[x]); } int main() { for(int i=1;i<=100001;i++) a[i]=i,vis[i]=0; bool ok=0; int maxn=0; while(1) { int x,y; scanf("%d%d",&x,&y); vis[x]=vis[y]=1; maxn=max(maxn,max(x,y)); if(x==-1&&y==-1)return 0; if(x==0&&y==0) { int ans=0; for(int i=1;i<=maxn;i++) if(a[i]==i&&vis[i])ans++; if(ans>1)ok=1; if(!ok)puts("Yes"); else puts("No"); ok=0; for(int i=1;i<=100001;i++) a[i]=i,vis[i]=0; } int tx=x,ty=y; x=fa(x),y=fa(y); if(x==y&&tx!=ty) { ok=1;continue; } else a[y]=x; } }
原文:http://blog.csdn.net/dongshimou/article/details/36886557