Skip to content

并查集

约 104 个字 42 行代码 预计阅读时间 1 分钟

Disjoint Set 并查集

等价关系R的三个性质:

  • Reflexive 自反性：
    • \(a\ R\ a,for\ all\ a\in S\)
  • Symmetric 对称性:
    • \(a\ R\ b\ if\ and\ only\ if\ b\ R\ a\)
  • Transitive 传递性：
    • \(a\ R\ b\ and\ b\ R\ c\ implies\ that\ a\ R\ c\)

一般将root的值设为其树的大小的负值。

给长度为N的Union(数组实现)赋初值(即全为-1)

1
2
3
4
#include<srting.h>
int *uni=(int*)malloc(N*sizeof(int));
memset(uni,-1,sizeof(uni));
//对于整数数组，memset函数只能赋初值0或-1，请务必注意

优化Find算法：路径压缩

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
//优化过的find算法，找root的时候顺便减少了depth
//递归版本
int Find ( int X , DisjSet S ){
    if ( S[ X ] <= 0 )
        return X;
    else 
        return S[ X ] = Find( S[ X ], S );
}
---
//神的简化版本：
int find(int x) { 
    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
//迭代版本
int  Find ( int  X, DisjSet  S ){   
    int  root,trail,lead;

    for ( root = X; S[ root ] > 0; root = S[ root ] );  // find the root
    for ( trail = X; trail != root; trail = lead ) {
       lead = S[ trail ] ;  
       S[ trail ] = root ;  
    }  //把路上遇到的节点全连接到root上
    return  root ;
}

合并 Union

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void SetUnion(int n1, int n2, int S)
{
    int root1, root2;
    root1 = Find(n1,S);
    root2 = Find(n2,S);
    if (-S[root1] > -S[root2]) {
        S[root1]+=S[root2];
        S[root2]=root1;
    } else {
        S[root2]+=S[root1];
        S[root1]=root2;
    }
}
//按大小合并的Union并查集，任何节点的深度均不会超过$log_2 N$
Comments: