并查集.cpp

高效率的并查集。 使用rank来优化。

#include    <iostream>
const       int            MaxN = 50000 + 1;
int        p[MaxN] , n , m , ans , x, y , Count , Rank[MaxN];
void       Make_Set(int x)
{
           p[x] = x;
           Rank[x] = 0;
}
void       LINK(int x , int y)
{
           if (Rank[x] > Rank[y])
                  p[y] = x;
            else
            {
                  p[x] = y;
                  if (Rank[x] == Rank[y])  Rank[y]++;
            }           
}
int       FIND_SET(int x)
{
            if (x != p[x]) 
                 p[x] = FIND_SET(p[x]);
            return p[x];           
}
void        UNION(int x , int y)
{
            LINK(FIND_SET(x) , FIND_SET(y) );           
}
int        main()
{
           int   i;
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
           while(scanf("%d%d",&n,&m)&&(n!=0||m!=0))
           {
                   Count++;
                   for(i = 1 ; i <= n ; i++) Make_Set(i);
                   for(i = 1 ; i <= m ; i++)
                   {
                          scanf("%d%d",&x,&y);
                          UNION(x,y);    
                   }                  
                   ans = 0;            
                   for(i = 1 ; i <= n ; i++)
                   if (p[i] == i) ans++;       
                   printf("Case %d: %d\n",Count,ans);
           }
           return 0;           
}