今天仿照一个教程做了一个并查集（改进型，书上说用以消除退化树的），但发现有个不小的问题，各位帮忙看看~ 

这个并查集是比较简单的，只用一个parent的int数组，并查集里的元素就直接用数组的所在的下标，如下： 
                _____________ 
数组：       ¦-1 ¦-1 ¦-1 ¦-1 ¦ 
数组下标：0       1     2     3 

如果进行以下顺序合并： 
U(0,1) 
U(2,3) 
U(0,2) 
然后查找元素“0”在哪里（本来应该在3所在的集合里的），但结果却是4！？ 

以下是源代码： 



class UFSet
{
private:
    int *parent;
    int size;

public:
    UFSet(int mSize);
    ~UFSet(){   delete []parent;    }

    int Find(int i)const;        //返回包含 元素i 的子集合标示
    void Union(int x, int y);    //合并子集x 和 y
};

/************************** 函数实现体 *******************************/

UFSet::UFSet(int mSize)
{
    size = mSize;
    parent = new int[size];
    for(int i=0; i<size; i++)parent[i]=-1;
}

int UFSet::Find(int i) const
{
    int r,t,l;
    for(r=i; parent[r]>=0; r=parent[r]);
    if(i != r)
        for(t=i; parent[t]!=r; t=l){
            l = parent[t];
            parent[t] = r;
        }

    return r;
}

void UFSet::Union(int x, int y)
{
    int temp = parent[x] + parent[y];
    if(parent[x] >= parent[y]){
        parent[x] = y;
        parent[y] = temp;
    }
    else{
        parent[y] = x;
        parent[x] = temp;
    }
}

int main(int argc, _TCHAR* argv[])
{
    UFSet s(4);
    s.Union(0,1);
    s.Union(2,3);
    s.Union(0,2);
    cout<<s.Find(0)<<endl;
    return 0;
}