POJ2524-宗教问题-并查集-ACM

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int MAXN=50001;
 5 int pa[MAXN];
 6 int rank[MAXN];
 7 
 8 void make_set(int x){
 9     pa[x] = x;
10     rank[x] = 0;
11 }
12 
13 int find_set(int x){
14     if(x != pa[x]){
15         pa[x] = find_set(pa[x]);
16     }
17     return pa[x];
18 }
19 
20 void union_set(int x,int y){
21     x = find_set(x);
22     y = find_set(y);
23 
24     if(rank[x] >  rank[y]){
25         pa[y] = x;
26     }
27     else{
28         pa[x] = y;
29         if(rank[x] == rank[y]){
30             rank[y]++;
31         }
32     }
33 }
34 
35 
36 int main(void){
37     int n,m,kase=0,count;
38     while(scanf("%d%d",&n,&m) == 2 && n!=0 && m!=0){
39         int i;
40         for(i=1;i<=n;i++){
41             make_set(i);
42         }
43         for(i=0;i<m;i++){
44             int a,b;
45             scanf("%d%d",&a,&b);
46             union_set(a,b);    
47         }
48         count = 0;
49         for(i=1;i<=n;i++){
50             if(i == pa[i]){
51                 count++;
52             }
53         }
54         printf("Case %d: %d\n",++kase,count);
55     }
56     return 0;
57 }