并查集

  |  

摘要: 并查集的原理与代码模板

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文介绍并查集的原理和代码模板,最后针对并查集可以解决的几类问题,列出了一些题目列表。


$1 并查集

并查集是一种可以动态维护若干个不重叠的集合,并支持合并与查询的数据结构。它包含两个基本操作:

  • 查询 find(x),查询一个元素属于哪个集合。
  • 合并 union(x, y),把两个集合合并为一个集合。

集合的表示

在并查集中,我们用代表元的方法表示集合。也就是为每个集合选一个固定的元素,称其为代表元,作为整个集合的代表。

归属关系的表示

如果用数组,vec[x] 表示元素 x 所在集合的代表,那么可以快速查询元素的所属集合,但是合并时需要大量修改 vec 中的值。

如果用树形结构存储集合,树上的每个节点都是一个元素,树根为集合的代表元。则并查集是一个森林,此时我们仍然可以用数组维护这个森林。fa[x] 表示 x 的父节点,若 x 为根节点,则 fa[x] = x

基本操作

并查集支持合并和查询两个操作。下面我们看一下用森林维护并查集时,这两种操作具体是怎么做的。

在用 find(x) 查询 x 属于哪个集合时,需要从该元素开始,通过 fa 不断递归地访问父节点,直至到达树根,返回树根编号作为所属集合的 id。

用森林维护并查集时,合并操作 union(x, y) 只需要连接两个树根即可,也就是 fa[find(x)] = find(y)

为了提高查询效率,并查集可以引入路径压缩和按秩合并两种思想。

路径压缩

每次 find(x) 时,向上查找过程中会经过一些节点,把这些节点的父节点都设为 find(x) 找到的根,以后的查找再经过这个点的时候就可以一次找到根。

1
2
3
4
5
6
7
int _find(int x)
{
if(_father[x] == x)
return x;
else
return _father[x] = _find(_father[x]); // 路径压缩
}

按秩合并

额外维护一个 rank 数组,rank[x] 表示以 x 为根的子树的高度,合并时把较矮的树的树根连接到较高的树的树根上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int x, int y)
{
x = _find(x);
y = _find(y);
if(x == y) return;

// 此时 x, y 是所在树的根
if(_rank[x] < _rank[y])
_father[x] = y;
else
{
_father[y] = x;
if(_rank[x] == _rank[y])
++_rank[x];
}
}

也可以把秩定义为以 x 为根的子树的大小,此时按秩合并也称为启发式合并。这种思想在很多数据结构中都有应用,也就是把小的结构合并到大的结构中,只增加小的结构的查询代价。

使用路径压缩的并查集,查询的时间复杂度为摊销 $O(\log N)$,使用按秩合并的并查集,查询的时间复杂度为 $O(\log N)$,同时使用路径压缩和按秩合并的并查集,查询的时间复杂度为摊销 $O(\alpha (N))$,其中 $O(\alpha (N))$ 为反阿克曼函数,在 1975 年 R.E.Tarjan 的论文 《Efficiency of a Good But Not Linear Set Union Algorithm》 中给出了证明。

并查集解决的问题

并查集可以解决图上的以下问题:

  • 加边连通性:不断加边,同时问某两个点是否连通。
  • Kruskal 最小生成树
  • 连通分量:个数,大小
  • 环:判定,长度,个数

$2 模板题:547. 省份数量

有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

给你一个 $n \times n$ 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

提示:

1
2
3
4
5
6
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

示例 1:
输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2
示例 2:
输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3

代码 (C++,模板)

连通分量个数,内部用 _set_size 维护连通分量个数。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class UnionFindSet {
public:
UnionFindSet(int n)
{
_set_size = n;
_father = vector<int>(n, -1);
_rank = vector<int>(n, 0);
for(int i = 0; i < n; ++i)
_father[i] = i;
}

~UnionFindSet(){}

bool same(int x, int y)
{
return _find(x) == _find(y);
}

void merge(int x, int y)
{
x = _find(x);
y = _find(y);
if(x == y) return;

// 此时 x, y 是所在树的根
if(_rank[x] < _rank[y])
_father[x] = y;
else
{
_father[y] = x;
if(_rank[x] == _rank[y])
++_rank[x];
}

--_set_size;
}

int set_size()
{
return _set_size;
}

private:
vector<int> _father;
vector<int> _rank;
int _set_size;

int _find(int x)
{
if(_father[x] == x)
return x;
else
return _father[x] = _find(_father[x]); // 路径压缩
}
};

class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
int m = M.size();
if(m == 1) return 1;
UnionFindSet unionfindset(m);
for(int i = 0; i < m - 1; ++i)
for(int j = i + 1; j < m; ++j)
if(M[i][j] == 1)
unionfindset.merge(i, j);
return unionfindset.set_size();
}
};

$3 并查集的回滚

如果并查集要支持回滚操作,就是要把已经合并成一棵树的若干子树,恢复成此前的若干子树。需要开栈保存每次合并操作时,被合并的哪一个根(高度较小的那一个根)。后续通过栈里的信息回滚。

支持回滚操作就不能使用路径压缩了,因为路径压缩回改变节点与节点之间的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
stack<int> st; // 保存每次合并操作时被合并的根

void merge(int x, int y)
{
x = _find(x);
y = _find(y);
if(x == y) return;
// 此时 x, y 是所在树的根
if(_rank[x] < _rank[y])
{
_father[x] = y;
st.push(x); // x 被合并
}
else
{
_father[y] = x;
if(_rank[x] == _rank[y])
++_rank[x];
st.push(y); // y 被合并
}
--_set_size;
}

$4 题目汇总

(1) 加边连通性

不断加边,同时问某两个点是否连通。可以动态维护具有传递性的关系。

(2) Kruskal

(3) 连通分量

解决连通分量的判定、个数、属性、大小相关的问题。

连通分量判定

连通分量个数

连通分量属性

连通分量大小

(4) 环

解决环的判定、长度、大小相关的问题。


Share