例题洛谷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;
}
}
