1
#include<iostream>
2using namespace std;
3#define MAXN 50000
4
5int parent[MAXN+1];
6
7void init(int n)
8
{
9
int i;
10 for(i=1;i<=n;i++)
11 parent[i]=-1;
12
}
13
14
15int find(int x)
16{
17 if(parent[x]<0)
18 return x;
19 else return parent[x]=find(parent[x]);
20
21}
22
23void Union(int x,int y)
24{
25 int root1=find(x),
26 root2=find(y);
27 if(root1==root2) return;
28 if(parent[root1]<parent[root2])
29
{
30 parent[root1]+=parent[root2];
31 parent[root2]=root1;
32 }else{
33 parent[root2]+=parent[root1];
34 parent[root1]=root2;
35
}
36}
37
38
39int main()
40{
41 int n,m,x,y,i,k=1,sum;
42 memset(parent,-1,sizeof(parent));
43 while( scanf("%d%d",&n,&m)==2 && n!=0 )
44 {
45 sum=0;
46 while(m--)
47 {
48 scanf("%d%d",&x,&y);
49 Union(x,y);
50 }
51 for(i=1;i<=n;i++)
52 {
53 if(parent[i]<0)
54 sum++;
55 parent[i]=-1;
56 }
57 printf("Case %d: %d\n",k++,sum);
58 }
59 return 0;
60}
posted on 2009-04-22 20:20
wyiu 阅读(81)
评论(0) 编辑 收藏 引用 所属分类:
POJ