void Make_set(int n)
{
for(int i=0;i<=n;i++)
{
father[i]=i;
rank[i]=0;
}
}
int find(int x)
{
int k, j, r;
r = x;
while(r != parent[r]) //查找跟节点
r = parent[r]; //找到跟节点,用r记录下
k = x;
while(k != r) //非递归路径压缩操作
{
j = parent[k]; //用j暂存parent[k]的父节点
parent[k] = r; //parent[x]指向跟节点
k = j; //k移到父节点
}
return r; //返回根节点的值
}
void Union(int x,int y)
{
if(x==y)return;
if(rank[x]>rank[y])
{
father[y]=x;
}
else
{ //rank[x]<rank[y],也是father[x]=y,所以省略
if(rank[x]==rank[y])
{
rank[y]++;
}
father[x]=y;
}
}