并查集

等价关系：对称，自反，传递

等价类：集合划分

操作：

  1. 查：找当前集合属于哪一个等价类
  2. 并：合并两个等价类

实现：树

  • Union, Find操作仅涉及fa，故只需存储fa
  • 静态链表建树，S[element] = fa, s[root] = 0，set name = root index

应用：动态等价性问题 

Initialize N disjoint sets;
while (read in a ~ b) {
    if (!(Find(a) == Find(b))) Union the two sets;
}
while (read in a and b) {
    if (Find(a) == Find(b)) output(ture);
    else output(false);
}

操作：

  • SetUnion 
    void  SetUnion ( DisjSet S, SetType Rt1, SetType Rt2 ) {S [ Rt2 ] = Rt1 ;}
  • Find 
    SetType  Find ( ElementType X, DisjSet S )
{ for ( ; S[X] > 0; X = S[X] );return  X ;}

问题：合并的最坏情况导致其退化为单链，find操作\(T(N)=O(N)\).

解决1：按大小合并

实现：

  • 集合大小记录：S[root] = -size;
    • 由于节点编号均为正数，故使用负数来记录大小信息

引理：按大小合并时\(\text{height}(T)\leqslant\lfloor\log_2N\rfloor+1\)

时间复杂度：\(N\)次合并，\(M\)次查找，\(O(N+M\log_2N)\)

解决2：按高度合并

实现：S[root] = -height

路径压缩：让所有儿子都直接指向根，find操作复杂度降为\(O(1)\)

实现：在find同时压缩

SetType  Find ( ElementType  X, DisjSet  S ) {
    if ( S[ X ] <= 0 ) return  X;
    else return  S[ X ] = Find( S[ X ], S );
}
循环版本： 
SetType  Find ( ElementType  X, DisjSet  S )
{   ElementType  root,  trail,  lead;
    for ( root = X; S[ root ] > 0; root = S[ root ] )
        ;  /* find the root */
    for ( trail = X; trail != root; trail = lead ) { 
    // lead带着trail将路径上所有节点连上root
       lead = S[ trail ] ;   
       S[ trail ] = root ;   
    }  /* collapsing */
    return  root ;
}

Union-by-height无法和路径压缩合并使用：路径压缩导致树高改变

按秩（集合大小等指标）合并 + 路径压缩：

  • 引理：\(k_1M\alpha(M,N)\leqslant T(M,N)\leqslant k_2M\alpha(M,N)\)
    • 其中\(\alpha\)为Ackermann函数的反函数\(\alpha\leqslant4\)
\[ A(i,j)=\left\{\begin{array}{ll}2^j&i=1,j\geqslant1\\ A(i-1,2)&i\geqslant2,j=1\\ A(i-1,A(i,j-1))&i\geqslant2,j\geqslant2\end{array}\right. \]