并查集

例题洛谷P2978
用途：判断图中有几个连通块
1.int pre[1000]; 记录了每个人的上级是谁。如果一个人的上级就是他自己，那说明他就是队长，一个块只能有一个队长
2.查找

int find(int x)                       
{
   if(pre[r]==r)
        return r;
    else find(pre[r]);                   
}

3.合并

void join(int x,int y)                     
{
    int fx=find(x), fy=find(y);            
    if(fx != fy)                             
        pre[fx]=fy;                       
}

4.路径压缩
因为不关心连通的结构，有可能是个很长的链状结构，理想的状况是，所有人的上级都是自己队伍里面的队长，这样需要只要一次操作就能判断是否是一个队伍的。
因此，每次根据每个点查找到队长后将该点的上级设为队长。
同时为了使合并后的树不再退化，即合并后层数尽量不变，可以用rank[1000]表示树的层数

改进后的代码

int pre[1000];
int rank[1000];
//初始化
for(int i=0;i<n;i++)
{
   pre[i]=I;
   rank[I]=0;
}
//查找函数
int find(int x)     
{
   if(pre[x] == x){       
       return x;      
   }
   return pre[x] =find (pre[x]);   
}
//合并函数
void Union(int i,int j)
{
   i=find(i);
   j=find(j);
   if(i==j) return ;
   if(rank[i]>rank[j]) pre[j]=i;
   else
   {
       if(rank[i]==rank[j]) rank[j]++;  
       pre[i]=j;
   }
}