并查集

首先我们定义一个数组，用双亲表示法来表示各棵树（所有的集合元素个数总和为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;
    }
}