基础的并查集

 1 #include<stdio.h>
 2 int f[50005],sum;
 3 int find(int x)
 4 {
 5     if(f[x]!=x)
 6         f[x]=find(f[x]);
 7     return f[x];
 8 }
 9 void make(int a,int b)
10 {
11     int f1=find(a);
12     int f2=find(b);
13     if(f1!=f2)
14         {
15             f[f2]=f1;
16             sum--;
17         }
18 
19 }
20 int main()
21 {
22     int n,m,p=1,i;
23     while(scanf("%d%d",&n,&m)!=EOF)
24     {
25         if(n==0&&m==0)  break;
26         for(i=1;i<=n;i++)
27             f[i]=i;
28         sum=n;
29         for(i=1;i<=m;i++)
30         {
31             int a,b;
32             scanf("%d%d",&a,&b);
33             make(a,b);
34         }
35         printf("Case %d: %d\n",p++,sum);
36     }
37     return 0;
38 }