poj 2524 求连通分量（并查集模板题）

求连通分量

Sample Input

10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
Sample Output

Case 1: 1
Case 2: 7

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <cmath>

 # include <queue>

 # define LL long long

 using namespace std ;

 const int MAXN = ;

 int F[MAXN];

 int num[MAXN] ;

 int find(int x)//找x的祖先结点

 {

     if(F[x]==x) return x;

     return F[x]=find(F[x]);

 }

 void bing(int u,int v) //按秩合并

 {

     int x = find(u);

     int y = find(v);

     if(x == y)

         return ;

     if(num[x] >= num[y])

     {

         F[y] = x;

         num[x] += num[y];

     }

     else

     {

         F[x] = y;

         num[y] += num[x];

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin) ;

     int n , m ;

     int Case =  ;

     while(scanf("%d %d", &n , &m) != EOF)

     {

          Case++ ;

          if (n ==  && m == )

              break ;

          int i ;

          for(i =  ; i <= n ; i++)

          {

              F[i] = i ;

              num[i] =  ;

          }

         int u , v ;

         while(m--)

         {

             scanf("%d %d" , &u , &v) ;

             bing(u , v) ;

         }

         int res =  ;

         for(i =  ; i <= n ; i++)

             if (F[i] == i)

                res++ ;

         printf("Case %d: %d\n" , Case , res) ;

     }

     return ;

 }