hdoj 1232+hdoj 1272 （并查集）

//hdoj 1232

#include <iostream> using namespace std; int DisjSet[1001]; int ans; int Find(int X) { if(DisjSet[X]<0) return X; else return Find(DisjSet[X]); } void SetUnion(int Root1,int Root2) { Root1=Find(Root1); Root2=Find(Root2); if(Root1 != Root2){ ans--; /*按深度求并*/ if(DisjSet[Root2] < DisjSet[Root1] ) //Root2 is deeper set DisjSet[Root1] = Root2; else { if(DisjSet[Root1] == DisjSet[Root2]) DisjSet[Root1]--; DisjSet[Root2]=Root1; } } } int main() { int N,M; int i,X,Y; while(scanf("%d",&N)!=EOF && N){ scanf("%d",&M); ans=N-1; memset(DisjSet,255,sizeof(DisjSet)); for(i=0;i<M;i++){ scanf("%d%d",&X,&Y); SetUnion(X,Y); } printf("%d/n",ans); } return 0; }  

//hdoj 1272

思路：不仅需要判断是否有环，还需判断是否连通

#include <iostream> using namespace std; int set[100001]; int flag; int find(int x) { if(set[x]<0) return x; return set[x]=find(set[x]); //路径压缩 } void unionset(int a,int b) { int root1,root2; root1=find(a); root2=find(b); if(root1==root2){ flag=0; return ; } /*按大小求并 */ if(set[root1] <= set[root2]){ //root1 is bigger set, then add to root1 set[root1]+=set[root2]; set[root2]=root1; } else{ set[root2]+=set[root1]; set[root1]=root2; } } int main() { int a,b; int i,root; while(scanf("%d%d",&a,&b)!=EOF) { if(a==-1 && b==-1) break; memset(set,255,sizeof(set)); flag=1; while(a+b) { if(flag) unionset(a,b); scanf("%d%d",&a,&b); } if(flag){ flag++; for(i=1;flag && i<=10000;i++) if(set[i]< -1) flag--; } if(flag) printf("Yes/n"); else printf("No/n"); } return 0; }