poj 2524 Ubiquitous Religions 一简单并查集

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<set>
 5 #include<cstdio>
 6 using namespace std;
 7 int father[50005];
 8 int vis[50005];//用来标记出现过没有；
 9 void begin(int m)
10 {
11     for(int i=1;i<=m;i++)
12         {father[i]=i;vis[i]=0;}
13 
14 }
15 int find(int x)
16 {
17     if(father[x]!=x)
18     {
19         father[x]=find(father[x]);
20     }
21     return father[x];
22 }
23 int main()
24 {
25     int m,n,x,y,a,b,mm,ans,k=1;
26     while(scanf("%d %d",&m,&n) && m+n)
27     {   ans=0;mm=0;       //mm 统计的是出现的个数，减去就是没出现的个数；
28         begin(m);
29         for(int i=1;i<=n;i++)
30         {
31             scanf("%d %d",&x,&y);//输入尽量用scanf（344ms），cin（4688ms）差别略大啊；
32             if(x<=m && y<=m)
33             {
34                 a=find(x);b=find(y);//各找各的父亲；
35                    father[a]=b;
36                     if(vis[x]==0)   //标记统计出现过多少个数；
37                         {mm++;vis[x]=1;}
38                         if(vis[y]==0)
39                            {mm++;vis[y]=1;}
40             }
41         }
42         for(int i=1;i<=m;i++)              //统计共有几个集合，实在不好想，用了个笨方法；
43         {
44               if(father[i]==i && vis[i]==1)//父亲的父亲，是他本身，并且他已经出现过了
45                   ans++;
46         }
47         printf("Case %d: %d\n",k++,ans+m-mm);
48     }
49     return 0;
50 }