并查集……
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
#include <cstdio>int f[2010],n,m,x,y,fx,fy,ans;int sf(int
x){return
x==f[x]?x:f[x]=sf(f[x]);}int main(){ while(scanf("%d",&n)) { if(n==0)break; scanf("%d",&m); for(int
i=1;i<=n+1;i++)f[i]=i; for(int
i=0;i<m;i++){ scanf("%d%d",&x,&y); fx=sf(x);fy=sf(y); if(fx!=fy)f[fx]=fy; } ans=0; for(int
i=1;i<=n;i++) if(f[i]==i)ans++; printf("%d\n",ans-1); }} |
原文：http://www.cnblogs.com/forever97/p/3553232.html