http://poj.org/problem?id=2524
这道题就是并查集。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define maxn 50010 5 using namespace std; 6 int a[maxn]; 7 int n,m; 8 void init() 9 { 10 for(int i=1;i<=n;i++) 11 a[i]=i; 12 } 13 int find1(int x) 14 { 15 if(x!=a[x]) 16 a[x]=find1(a[x]); 17 return a[x]; 18 } 19 void merge1(int x,int y) 20 { 21 int fx=find1(x); 22 int fy=find1(y); 23 if(fx!=fy){ 24 a[fx]=fy; 25 n--; 26 } 27 } 28 int main() 29 { 30 int a,b,t=0; 31 while(scanf("%d%d",&n,&m)&&n&&m){ 32 init(); 33 for(int i=1;i<=m;i++){ 34 scanf("%d%d",&a,&b); 35 merge1(a,b); 36 } 37 t++; 38 printf("Case %d: ",t); 39 printf("%d ",n); 40 } 41 return 0; 42 }