http://blog.csdn.net/dellaserss/article/details/7724401
好厉害，好厉害。(*/ω╲*)
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 52011 Accepted Submission(s): 27728
#include<bits/stdc++.h> int pre[1000]; int find(int x){ int r=x; while(pre[r]!=r) r=pre[r]; int i=x,j; while(i!=r){ j=pre[i]; pre[i]=r; i=j; } return r; } int main(){ int n,m,p1,p2,i,total,f1,f2; while(scanf("%d",&n)&&n){ total=n-1; for(i=1;i<=n;i++){ pre[i]=i; } scanf("%d",&m); while(m--){ scanf("%d%d",&p1,&p2); f1=find(p1); f2=find(p2); if(f1!=f2){ pre[f2]=f1; total--; } } printf("%d\n",total); } return 0; }
2.ans++:
#include<bits/stdc++.h> using namespace std; int pre[1050]; bool t[1050]; int Find(int x){ int r=x; while(r!=pre[r]) r=pre[r]; int i=x,j; while(pre[i]!=r){ j=pre[i]; pre[i]=r; i=j; } return r; } void mix(int x,int y){ int fx=Find(x),fy=Find(y); if(fx!=fy){ pre[fy]=fx; } } int main(){ int n,m,a,b,i,j,ans; while(scanf("%d",&n)&&n){ for(i=1;i<=n;i++) pre[i]=i; scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d",&a,&b); mix(a,b); } memset(t,0,sizeof(t)); for(i=1;i<=n;i++) t[Find(i)]=1; for(ans=0,i=1;i<=n;i++) if(t[i]) ans++; printf("%d\n",ans-1); } return 0; }
1.total--一直没想明白，老大讲了一下:
total最开始是城市数-1，假设有1、2，因为1、2的父亲不一样（最开始当然父亲不一样，我这个智障，这里没想到。。。），就是要让1、2在一个集合，就是要让他们父亲一样，所以减1，（最开始都是没有路的）。现在1、2有路，所以要让他们父亲一样，就减1。。。
我还有一个智障的地方，n个点，从1-n，要有n，所以初始化要从i=1开始。。。
2.ans++的好想明白。
大佬orz，ヾ(≧O≦)〃嗷~
加油。
原文：http://www.cnblogs.com/ZERO-/p/6666974.html