并查集
 #include < stdio.h > 
#include 
< memory.h > 
 
const   int  MAX  =   100000 ;
 
class  UnionFindSet
  
{
 
public :
     
int  parent[MAX];
    UnionFindSet();
     
int     Union( int  x,  int  y);
     
int  Find( int  i);
}
 ;
UnionFindSet::UnionFindSet()
  
{
    memset(parent, 
- 1 , sizeof (parent));
}
 
 
int     UnionFindSet::Union( int  x,  int  y)
  
{
    x  
=  Find(x);
    y  
=  Find(y);
     
//  找出的根节点x,parent[x]中保存的是根为x的元素的个数的相反数; 
      int  temp  =  parent[x]  +  parent[y];
     
if (parent[x]  <=  parent[y])
      
{
        parent[y]  
=  x;
        parent[x]  
=  temp;
    }
 
      
else  {
        parent[x]  
=  y;
        parent[y]  
=  temp;
    }
 
     
return   0 ;
}
 
 
int  UnionFindSet:: Find( int  i)
  
{
     
if (parent[i]  <   0 )
         
return  i;
     
else  {
        parent[i]  
=  Find(parent[i]); // 压缩路径; 
          return  parent[i];
    }
 
}
 
  
/**/ /* 
int UnionFindSet::Find(int x)
{
     int i;
     for(i = x; parent[i] >= 0; i = parent[i]);//搜索根节点;
     while(i!=x)//路径压缩;
     {
          int tmp = parent[x];
          parent[x] = i;
          x = tmp;
     }
     return i;
}
 
*/
 
 
int  main()
  
{
     
return   0 ;
}