并查集

2022

优雅的数据结构，简洁的实现方式.

0 简介

并查集(disjoint-set data structure)是一种数据结构，可以查询元素所在的集合，以及合并两个不相交的集合. 其操作有: 添加集合、查询、合并.

初始化

在同一个集合中的元素，应有一个集合中的元素作为该集合的代表；而新加入的元素可以以集合中的元素为父节点，这样同一集合中的元素就在一棵树中，树的根节点为该集合的代表. 所以，用如下数组来表示：

1
2
3
int rep[N];
for(int i = 0; i < N; i++)
    rep[i] = i;

其中，元素$i$的父节点为$\text{rep}[i]$.

1 朴素的实现

查询

1
2
3
4
int find(int x) {
    if(rep[x] == x) return x;
    else return find(rep[x]);
}

合并

1
2
3
4
// merge j's set with i's set
void merge(int i, int j) {
    rep[find(i)] = find(j);
}

2 高效的实现

2.1 路径压缩

修改$find$函数，在查询过程中，将$x$的父节点设置为根节点，使$x$到达根节点路径尽量短.

1
2
3
4
5
6
7
int find(int x) {
    if(rep[x] == x) return x;
    else {
        rep[x] = find(rep[x]);
        return rep[x];
  }
}

2.2 按秩合并

用秩($rank$)表示节点的深度，合并时，将秩较小的合并到较大的上面.

初始化

1
2
3
4
5
6
int rep[N];
int rank[N];
for(int i = 0; i < N; i++) {
    rep[i] = i;
    rank[i] = 0;
}

合并

1
2
3
4
5
6
7
void merge(int i, int j) {
    int x = find(i), y = find(j);
    if(rank[x] < rank[y]) rep[x] = y;
    else rep[y] = x;
    if(rank[x] == rank[y] && x != y)
        rank[x++];
}

参考

[1] 维基百科

[2] 知乎