学步园

 
并查集：(union-find sets)是一种简单的用途广泛的集合.
并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数、最小公共祖先、带限制的作业排序，还有最完美的应用：实现Kruskar算法求最小生成树。其实，这一部分《算法导论》讲的很精炼。

 

    一般采取树形结构来存储并查集，在合并操作时可以利用树的节点数(加权规则)或者利用一个rank数组来存储集合的深度下界--启发式函数，在查找操作时进行路径压缩使后续的查找操作加速。

   
这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M
Alpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是线性的。

它支持以下三种操作:

    make_set(x)
//构造函数。将并查集中n个元素初始化为n个只有一个单元素的子集合。

    find_set(x)
//搜索操作。搜索元素x所在的集合,并返回该集合的名字--根节点(或称集合代表)。

    union_set(x,
y) //合并操作。把含有x的集合与含有y的集合合并。(先判断为不相交集合)
    集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。   

    为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合

 

三种操作自己的模板：

   
const int Max = 100000;

   
int parent[Max], rank[Max];

 

   
void make_set(int x){

       
parent[x] = x;

       
rank[x] = 0;

   
}

 

   
int find_set(int x){

       
if(x != parent[x])

           
parent[x] = find_set(parent[x]);

       
return parent[x];

   
}

 

   
void union_set(int x, int
y){  
//  不含按秩合并的版本。很多时候按秩合并的优化效果不明显。

        
x = find_set(x);

        
y = find_set(y);

        
if(x == y) return;

         parent[y]
= x;

   
}

 

   
void union_set(int x, int
y){  
//  含按秩合并的版本。

        
x = find_set(x);

        
y = find_set(y);

        
if(x == y) return;

        
if(rank[x] > rank[y])

            
parent[y] = x;

        
else{

            
parent[x] = y;

            
if(rank[x] == rank[y])

                
rank[y] ++;

        
}

   
}