O(1) 的小乐

    并查集：(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;
}