题意：判一个无向图无环且处处连通
思路：并查集，，trap 可能直接输入0 0
而且….合并的时候按某一个方向会爆栈，爆了好几次…下次考虑一下直接递归找祖先吧
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N =1e5+1e2;int fa[N];int getf(int x){return x==fa[x]? x:fa[x]=getf(fa[x]);}int Merge(int x,int y){int t1=getf(x);int t2=getf(y);if(t1==t2) return false;fa[t2]=t1;return true;}bool vis[N];bool flag;int cnt;void ini(){for(int i=1;i<100005;i++) fa[i]=i;flag=true;cnt=0;memset(vis,0,sizeof(vis));}int main(){int u,v;while(scanf("%d%d",&u,&v),~u){if(!(u||v)){puts("Yes");continue;}ini();vis[u]=vis[v]=true;flag=Merge(u,v);while(scanf("%d%d",&u,&v),(u||v)){vis[u]=vis[v]=true;if(!flag) continue;flag=Merge(u,v);}if(flag)for(int i=1;i<100005;i++)if(vis[i]&&fa[i]==i) cnt++;if(cnt>1)flag=0;if(flag) puts("Yes");else puts("No");}return 0;}
可是却依旧为对方擦去嘴角的油渍。
