并查集

并查集

并查集是什么

并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作:

  • 查询元素 a 和元素 b 是否属于同一组。
  • 合并元素 a 和元素 b 所在的组。

并查集的结构

为了快速查询,一般用树形结构实现,每个元素对应一个节点,每个分组对应一棵树。并查集中,哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注,整体的树形结构(分组)很重要。

初始化

准备 n 个节点来表示 n 个元素。

合并

将一个组的根向两一个组的根连边,合并两棵树。

查询

查询两个节点是否属于同一组,只需要沿着节点所在树往上走,来查询这两个节点是否有同一个根。

并查集的优化方法

为了避免数中最差情况的发生(每个节点只有一个后继节点)。按如下方法进行优化:

  • 对于每棵树,记录这棵树的高度(rank)。
  • 合并时,如果两棵树的 rank 不同,从 rank 小的向 rank 大的连边。

此外,通过路径压缩,使得并查集更为高效。对每个节点,一旦向上走一到了一次根节点,就将这个节点到父亲的边改为直接连向根。

在此之上,不仅仅是所查询的节点,查询过程中,向上经过的所有节点,都改为直接连向根。

为了简单起见,即使树的高度发生了变化,也不修改 rank 的值。

并查集的复杂度

优化后的并查集效率非常高,对 n 个元素的并查集进行一次操作的复杂度是 \(O(\alpha(n))\)\(\alpha(n)\)是阿克曼函数的反函数,比\(O(logn)\)还要快。

并查集的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int par[MAX_N], rank[MAX_N]; 

void init(int n){
for (int i = 0; i < n; ++i) {
par[i] = i;
rank[i] = 0;
}
}

int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]); // 路径压缩
}

void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) { // 树高度优化
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y])
++rank[x];
}
}

bool same(int x, int y) {
return find(x) == find(y);
}
# C++

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×