首先我们定义一个数组，用双亲表示法来表示各棵树（所有的集合元素个数总和为N)
int Tree[N];
用Tree[i]表示结点i的双亲结点，若Tree[i]为-1则表示根结点
那么为了查找到结点x 的根结点，设立了一下函数
递归方法：
int FindRoot(int x)
{
if(Tree[x]==-1) return x; //如果x的双亲结点节点是-1,那么它就是根结点、
else return FindRoot(Tree[x]); // 否则，让双亲结点找根结点；
}
非递归方法：
int FindRoot(int x)
{
if(Tree[x]==-1) return x; //如果x的双亲结点节点是-1,那么它就是根结点、
else {
int tmp =Tree[x];
while(tmp!=-1)
{
x=tmp;
tmp=Tree[x]; //不断的找双亲结点，直到找到根结点；
}
return x; //因为Tree[x]==-1;
}
}
为了让树的高度降低，我们考虑路径压缩，让路径上的结点都指向根结点，以上两个代码变成
int FindRoot(int x)
{
if(Tree[x]==-1) return x; //如果x的双亲结点节点是-1,那么它就是根结点、
else {
int tmp =Tree[x];
while(tmp!=-1)
{
t=tmp;
tmp=Tree[t]; //不断的找双亲结点，直到找到根结点；
}//t为根结点
while(Tree[x]!=-1)
{
Tree[x]=t;
x=Tree[x];
}
return t;
}
}
int FindRoot(int x)
{
if(Tree[x]==-1) return x;
else {
int tmp=FindRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
