資料結構-并查集

适合需要反複用到查詢某個元素歸屬于哪個集合的運算。

初始化時每個元素自成為單元素集合，parent均為-1。此後parent[x]>0時表示元素x的父在數組中的下标；parent[x]<0時表示以元素x為根的集合的元素個數

Find操作可以查詢元素歸屬哪個集合，搜尋并傳回包含元素x的根即可，有兩種方法：

（1）非遞歸方法：while(parent[x]>=0) x=parent[x];

（2）遞歸方法：x為根時直接傳回x，否則繼續Find(parent[x])遞歸找x的父的根

Union操作進行集合合并，預設把元素Root2嫁接到Root1上：parent[Root1]+=parent[Root2]; parent[Root2]=Root1;

執行一次Union操作需要O(1)，而n-1次Union操作可以在O(n)内完成。

性能不好，可能會産生退化了的樹。此時Find操作需要從被搜尋元素出發，沿父指針鍊走到根，完成Find(i)的時間複雜度為O(i)，而完成n次搜尋需要的總時間為O(n^2)

可以使用權重規則得到改進Union操作，使用結點個數探查法求兩個UFSets類集合的并，結點個數少的集合嫁接到結點個數多的集合上。執行一次WeightedUnion操作的時間比執行一次Union的時間稍多，但仍在常量界限O(1)範圍内。

折疊規則壓縮路徑的算法CollapsingFind：如果元素j是從元素i到根的路徑上的一個結點，并且元素j的父結點不是根，則把元素j的父結點置為根

const int DefaultSize=10;
class UFSets{
public:
    UFSets(int sz=DefaultSize);
    ~UfSets(){delete []parrent;}
    UFSets& operator=(UFSets& R);
    void Union(int Root1,int Root2);
    int Find(int x);   
    void WeightedUnion(int Root1,int Root2);
    int CollapsingFind(int i);
private:
    int *parent;
    int size;
}

UFSets::UFSets(int sz){
    size=sz;
    parent=new int[size];
    for(int i=0;i<size;i++) parent[i]=-1;  //初始化時每個元素自成為單元素集合
}

int UFSets::Find(int x){
    //非遞歸方法，搜尋并傳回包含元素x的根
    while(parent[x]>=0) x=parent[x];
    return x;
    
    //  一種遞歸方法，x為根時直接傳回x，否則遞歸找x的父的根
    //  if(parent[x]<0) return x;
    //  else return Find(parent[x]);
}

void UFSets::Union(int Root1,int Root2){
    parent[Root1]+=parent[Root2];
    parent[Root2]=Root1;
}

void UFSets::WeightedUnion(int Root1,int Root2){
    int r1=Find(Root1),r2=Find(Root2),temp;
    if(r1!=r2){
        temp=parent[r1]+parent[r2];
        if(parent[r2]<parent[r1]){  //r2結點個數更多
            parent[r1]=r2;
            parent[r2]=temp;
        }
        else{
            parent[r2]=r1;
            parent[r1]=temp;
        }
    }
}

int UFSets::CollapsingFind(int i){
    for(int j=i;parent[j]>=0;j=parent[j]);  //在包含i的樹中搜尋根j
    while(i!=j){         //将從j到根的路徑上所有結點都變成根的子女
        int temp=parent[i];
        parent[i]=j;
        i=temp;
    }
    return j;
}