并查集

并查集森林

并查集森林是一种将每一个集合以树表示的数据结构，其中每一个节点保存着到它的父节点的引用（见意大利面条堆栈）。这个数据结构最早由Bernard A. Galler和Michael J. Fischer于1964年提出，但是经过了数年才完成了精确的分析。
在并查集森林中，每个集合的代表即是集合的根节点。“查找”根据其父节点的引用向根行进直到到底树根。“联合”将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。实现这样操作的一种方法是
 function MakeSet(x)
     x.parent := x
 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot
这是并查集森林的最基础的表示方法，这个方法不会比链表法好，这是因为创建的树可能会严重不平衡；然而，可以用两种办法优化。
第一种方法，称为“按秩合并”，即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。在这个算法中，术语“秩”替代了“深度”，因为同时应用了路径压缩时（见下文）秩将不会与高度相同。单元素的树的秩定义为，当两棵秩同为的树联合时，它们的秩。只使用这个方法将使最坏的运行时间提高至每个MakeSet、Union或Find操作。优化后的MakeSet和Union伪代码：
 function MakeSet(x)
     x.parent := x
     x.rank   := 0
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return

     // x和y不在同一个集合，合并它们。
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1
第二个优化，称为“路径压缩”，是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上；他们都有同样的表示方法。为了达到这样的效果，Find递归地经过树，改变每一个节点的引用到根节点。得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。这儿是Find：
 function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent
这两种方法的优势互补，同时使用二者的程序每个操作的平均时间仅为，是的反函数，其中是急速增加的阿克曼函数。因为是其的反函数，故在十分巨大时还是小于5。因此，平均运行时间是一个极小的常数。
实际上，这是渐近最优算法：Fredman和Saks在1989年解释了的平均时间内可以获得任何并查集。

主要操作

需要注意的是，一开始我们假设元素都是分别属于一个独立的集合里的。

合并两个不相交集合

操作很简单：先设置一个数组(数组)Father[x]，表示x的“父亲”的编号。
那么，合并两个不相交集合的方法就是，找到其中一个集合最父亲的父亲（也就是最久远的祖先），将另外一个集合的最久远的祖先的父亲指向它。
Pascal代码：
procedure Union(x,y:integer);{其中GetFather是下面将讲到的操作}
 var fx,fy : integer;
  begin
     fx := getfather(x);
     fy := getfather(y);
     If fx<>fy then father[fx] := fy;{指向最祖先的祖先}
  end;
C语言代码表示形式:
void Union(int x,int y){
    fx = getfather(x);
    fy = getfather(y);
    if(fy!=fx)
       father[fx]=fy;}

判断两个元素是否属于同一集合

仍然使用上面的数组。则本操作即可转换为寻找两个元素的最久远祖先是否相同。寻找祖先可以采用递归实现，见后面的路径压缩算法。
Pascal代码：
Function Same(x,y:integer):boolean;begin
  Same:=GetFather(x)=GetFather(y);end;
C代码：
bool same(int x,int y){
   return getfather(x)==getfather(y);}/*返回true 表示相同根结点，返回false不相同*/

路径压缩

刚才我们说过，寻找祖先时采用递归，但是一旦元素一多起来，或退化成一条链，每次GetFather都将会使用的复杂度，这显然不是我们想要的。
对此，我们必须要进行路径压缩，即我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。这就是路径压缩了。使用路径压缩的代码如下：
Pascal 语言的实现：
Function getfather(v:integer):integer;
  begin
    if (father[v]=v) then
      getfather:=v
    else
      begin
        father[v]:=getfather(father[v]);{路径压缩}
        getfather:=father[v];
      end;
  end;
C 语言的实现：
int getfather(int v){
    if (father[v]==v)
      return v;
    else
    {
        father[v]=getfather(father[v]);//路径压缩
        return father[v];
     }}

Rank合并

合并时将元素所在深度小的集合合并到元素所在深度大的集合。
Pascal 语言的实现：
function judge(x,y:integer):boolean;
 var fx,fy : integer;
  begin
     fx := getfather(x);
     fy := getfather(y);
     If fx=fy then 
       exit(true)
     else 
       judge := false;
     if rank[fx]>rank[fy] then
       father[fy] := fx
     else begin
       father[fx] := fy;
       if rank[fx]=rank[fy] then 
         inc(rank[fy]);
     end;
  end;
初始化：
fillchar(rank,sizeof(rank),0);
C 语言的实现：
void judge(int x ,int y){
     fx = getfather(x);
     fy = getfather(y);

     if (rank[fx]>rank[fy])
        father[fy] = fx;
     else
     {
        father[fx] = fy;
        if(rank[fx]==rank[fy])
           ++rank[fy]; //重要的是祖先的rank，所以只用修改祖先的rank就可以了，子节点的rank不用管
     }}
初始化：
memset(rank,0,sizeof(rank));

时间复杂度

同时使用路径压缩、按秩（rank）合并优化的程序每个操作的平均时间仅为，其中  是  的反函数， 是急速增加的阿克曼函数。因为  是其反函数，故  在  十分巨大时还是小于。因此，平均运行时间是一个极小的常数。实际上，这是渐近最优算法：Fredman 和 Saks 在 1989 年解释了 的平均时间内可以获得任何并查集。

空间复杂度

（为元素数量）