并查集：(union-find sets)是一種簡單的用途廣泛的集合. 并查集是若干個不相交集合，能夠實現較快的合并和判斷元素所在集合的操作，應用很多，如其求無向圖的連通分量個數、最小公共祖先、帶限制的作業排序，還有最完美的應用：實現Kruskar算法求最小生成樹。

一般采取樹形結構來存儲并查集，在合并操作時可以利用樹的節點數(加權規則)或者利用一個rank數組來存儲集合的深度下界--啟發式函數，在查找操作時進行路徑壓縮使后續的查找操作加速。這樣優化實現的并查集，空間復雜度為O(N)，建立一個集合的時間復雜度為O(1)，N次合并M查找的時間復雜度為O(M Alpha(N))，這里Alpha是Ackerman函數的某個反函數，在很大的范圍內這個函數的值可以看成是不大于4的，所以并查集的操作可以看作是線性的。
它支持以下三種操作:
－Union (Root1, Root2) //合并操作；把子集合Root2和子集合Root1合并.要求：Root1和 Root2互不相交,否則不執行操作.
－Root(x) //搜索操作；搜索元素x所在的集合,并返回該集合的名字--根節點.
－MakeSet (N) //構造函數。將并查集中s個元素初始化為s個只有一個單元素的子集合.

Union分為兩個版本，Union1是將parent域充分利用，其中Parent為正數時表示該節點的父節點下標，為負數時表示該節點為一個根節點，其絕對值為該集合包含的節點總數。  Union2版本是將rank利用，保存樹的高度。

Del1 是狹義上的刪除操作。(一次刪除后不再使用) Del2是廣義上的刪除操作，利用了一個Mapping數組來保存映射信息

當使用Del2的時候， 各個函數的調用方式是：Union1(Mapping[a],Mapping[b]);MakeSet(N) 如果顯式調用Root，也需要Mapping[x]; Root(Mapping[x]);

綜上，一般不涉及刪除操作，使用的是MakeSet(N)  Root(x) Union1()

如果涉及刪除操作，使用的是MakeSet(N) Root(Mapping[x])  Union1(Mapping[x],Mapping[y]) ,Del2[x]; //注意這里是Del[x];

reshape()來統計各個并查集分量塊，當操作都進行完了之后，才進行統計的！

Sosi實現：應用的版本不同。。

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 500001
struct
{
    int parent;       //標記父節點，如果parent為負數則表示是父節點，負數的絕對值表示此塊內節點數目
    int rank;         //rank 為樹高
    bool flag;        //標記是否被刪除 0 未被刪除，1 被刪除  如果引入刪除操作，rank樹高性質被破壞
}UFS[MAXN];           //UnionFindSet   UFS
int Mapping[MAXN];     //映射數組，為了進行刪除元素。
vector<int> UFSSet[MAXN];
int Dmax;

//其中Parent為正數時表示該節點的父節點下標，為負數時表示該節點為一個根節點，其絕對值為該集合包含的節點總數。
//rank表示權值，在不同問題中有不同的含義。
void MakeSet(int N)             /* 初始化 */
{
    for(int i=0;i<N;i++)             //0-indexed
    {
        UFS[i].parent=-1;        /* 開始每個節點單獨構成一個集合 */
        UFS[i].rank=0;           /* 權值視具體情況付初值 */
        UFS[i].flag=0;
        Mapping[i]=i;
    }
}

int Root(int x)     /* 查找包含接點x的集合的根節點 */
{
    int i=x,temp;
    while(UFS[i].parent>=0)
        i=UFS[i].parent;
    while(i!=x)     /* 壓縮路徑以提高以后檢索效率 */
    {
        temp=UFS[x].parent;            
        UFS[x].parent=i;                        //直接將x的祖先命為根節點
        x=temp;                                 //繼續處理x的原祖先
    }
    return i;
}

/*
Union1 的優點是能把并查集數某顆樹的節點數找到，在parent域中
且rank域空缺，可以去掉
如果使用，可以賦給rank域額外信息
*/
void Union1(int a,int b)     /* 合并a和b所在的集合 */
{
    int x,y;
    x=Root(a);
    y=Root(b);
    if(x==y) return;
    if(UFS[x].parent<UFS[y].parent)  
        UFS[x].parent+=UFS[y].parent,UFS[y].parent=x;    /* 始終將較小樹作為較大樹的子樹 */
    else
        UFS[y].parent+=UFS[x].parent,UFS[x].parent=y;

}
/*
Union 2 的優點是把樹高可以統計出來。。此時rank被占用
*/
void Union2(int a, int b)     //將rank較大的作為父節點
{
    int x = Root(a), y = Root(b);
    if( x == y ) return ;
    if( UFS[x].rank > UFS[y].rank ) UFS[y].parent = x;
    else{
        UFS[x].parent = y;
        if( UFS[x].rank == UFS[y].rank ) UFS[y].rank++;
    }
}
//此時的刪除只是狹義上的刪除，看1號節點被刪除之后，當下一次被添加的時候是什么性質了
//此時需要維護一個映射表！
//當新來一個元素之后，我們首先都是先進行映射！Mapping[]將所有的標號i修改成為Mapping[i];
//初始化Mapping為i；
void Del1(int x)           
{
    if(UFS[x].parent==-1)            //獨立頂點
        UFS[x].flag=true;
    else
    {
        if(UFS[x].parent>=0)         //葉子節點
        {
            UFS[x].flag=true;
            int i=x;
            while(UFS[i].parent>=0)
                i=UFS[i].parent;
            UFS[i].parent+=1;
        }
        else
            UFS[x].parent+=1,UFS[x].flag=true;      //并查集集合頂點
    }
}
void Del2(int x)   
{
    int initialx=x;               //便于修改一開始的x

    if(UFS[x].flag==true)         //已被刪除
        x=Mapping[x];

    if(UFS[x].parent==-1)            //獨立頂點
        UFS[x].flag=true;
    else
    {
        if(UFS[x].parent>=0)         //葉子節點
        {
            UFS[x].flag=true;
            int i=x;
            while(UFS[i].parent>=0)
                i=UFS[i].parent;
            UFS[i].parent+=1;
        }
        else
            UFS[x].parent+=1,UFS[x].flag=true;      //并查集集合頂點
    }

    Mapping[initialx]=Dmax;
    Mapping[Dmax]=Dmax;
    UFS[Dmax].parent=-1;
    UFS[Dmax].rank=0;
    UFS[Dmax].flag=0;

    Dmax++;
}
void reshape()
{
    //我們默認此處存儲為0-indexed
    int UFSBlock=0;
    for(int i=0;i<Dmax;i++)
    {
        if(UFS[i].parent<-1||((UFS[i].parent==-1) && (UFS[i].flag==0)))  //如果一個節點被刪除
        {
            UFSBlock++;
            UFSSet[0].push_back(i);
        }
    }
    for(int i=0;i<Dmax;i++)
    {
        if(UFS[i].flag==0)             //i號節點未被刪除
        {
            int x=Root(i);             //找到i號根節點
            for(int j=0;j<UFSSet[0].size();j++)         //根節點編號
            {
                if(x==UFSSet[0][j])
                {
                    UFSSet[j+1].push_back(i);
                    break;
                }
            }
        }
    }
    cout<<" 索引編號：";
    for(int i=0;i<UFSSet[0].size();i++)
        cout<<UFSSet[0][i]<<"    ";
    cout<<endl;

    for(int i=1;i<=UFSBlock;i++)
    {
        cout<<" BLOCK "<<i<<endl;
        for(int j=0;j<UFSSet[i].size();j++)
        {
            cout<<UFSSet[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"UFSBlock Num "<<UFSBlock<<endl;
}

/*
1 如果涉及到刪除操作，那么各個函數的調用方式是：
Union(Mapping[a],Mapping[b]);
MakeSet(N)
如果顯式調用Root，也需要Mapping[x]; Root(Mapping[x]);
*/
int main()
{
    int N=7;  //7個點
    MakeSet(N);
    Dmax=N;
    Union1(Mapping[1],Mapping[0]);
    Union1(Mapping[1],Mapping[2]);
    Union1(Mapping[3],Mapping[4]);
    Union1(Mapping[1],Mapping[4]);
    Del2(0);
    Del2(5);
    Del2(0);
    Del2(0);
    Union2(Mapping[0],Mapping[5]);
    for(int i=0;i<Dmax;i++)
    {
        if(UFS[i].flag==1)
        {
            cout<<"Index"<<i<<" be deleted"<<endl;
            cout<<"Index  "<<i<<"  parent   "<<UFS[i].parent<<"   rank  "<<UFS[i].flag<<endl;
        }
        else
            cout<<"Index  "<<i<<"  parent   "<<UFS[i].parent<<"   rank  "<<UFS[i].flag<<endl;

    }
    reshape();
    return 0;
}