本文简单总结并查集。
适用场景 ¶
并查集是非常简单的数据结构,代码简短而优美。
适合具有传递性关系的问题,尤其是连通性问题。
结构定义 ¶
并查集是一颗森林,由多颗树组成,每一颗树代表一个集合。
每个集合由树的根节点作为代表元,两个节点在同一个集合中(也就是连通)的话,它们的代表元(也就是根节点)是相同的。
结构的 C++ 定义如下,一般开静态数组来存储即可:
class UnionFind {
// 父节点数组 pa[i] 表示节点 i 的父节点下标
std::vector<int> pa;
// 大小数组 sizes[i] 表示以 i 作为根的集合内的元素个数
std::vector<int> sizes;
// 连通分量数量,即互不相连的孤岛数量
int c;
};
其中:
- 每个节点用一个数字来表示,也就是下标。
- 数组
pa
中存放节点的父节点的下标,特殊地,根节点的父节点定义为自身。 - 数组
sizes
存放树的大小,对于树的根节点才有意义。 - 连通分量
c
其实就是森林中树的个数(互不相交的集合的个数)。
比如下图中,共有 2
个连通分量,其根分别是 1
和 4
,各个节点都指向了其父节点,最终指向所在集合的根:
最开始,每个节点都初始化为一颗单独的树,大小均为 1
,此时连通分量就是 n
:
explicit UnionFind(int n)
: pa(std::vector<int>(n)), sizes(std::vector<int>(n, 1)), c(n) {
// 初始化: 自己作为父节点
for (int i = 0; i < n; i++) pa[i] = i;
}
核心操作只有两个:查询 和 合并。
find 和 路径压缩 ¶
Find
查询操作的函数定义是:
找到节点
x
所在集合的根。
只需递归向上寻找:
x
所在集合的根,就是其父节点所在集合的根。除非,
x
本身就是一个根。
用代码来表示就是:
int Find(int x) {
if (pa[x] == x) return x; // 根的父节点是本身
return Find(pa[x]);
}
目前都很好理解,那么,如果一旦找到了 x
的根,可以把 x
直接嫁接到根上,下次找就更快了。
这种把查询结果利用起来,直接拉近节点和根距离的办法,就是所谓的「路径压缩」。
用代码来表示就是:
// 查找一个节点的根节点
int Find(int x) {
if (pa[x] == x) return x;
pa[x] = Find(pa[x]); // 重设 x 的父节点到根
return pa[x];
}
这样,原本向上递归的路径上的所有节点,都会直接嫁接到根下面去,如下图所示,节点 4
向上找根的过程:
经过路径压缩后,树会变地更扁平,下一次 Find
也会更迅速。
union 和 按大小合并 ¶
Union
合并操作的函数定义是:
合并两个节点
a
和b
所在的集合。
首先,要先分别找出两个节点的集合的根,这只需利用前面所说的 Find
函数。
然后把其中一个根的父节点指向另一个作为其新的父节点,代码会很简洁:
void Union(int a, int b) {
pa[Find(b)] = Find(a);
}
不过,有的时候,合并后的树会变地不平衡。
其实,谁当新的根无所谓,只要合并后属于同一个集合就可以了。我们只关心连通性。
一种办法是,把更小的树合并到更大的树上去。
下图中,左边的的合并方式明显更好一些,合并后的树会更低。
用代码来表示就是:
void Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return; // 已经在同一集合
if (sizes[a] > sizes[b]) { // 把 b 并入 a
pa[b] = a;
sizes[a] += sizes[b];
} else {
pa[a] = b;
sizes[b] += sizes[a];
}
c--; // 连通分量减一
}
注意,其中也顺便维护了:
- 树的大小,只需维护新的根的大小
- 连通分量,每次合并后整体上就会少一个集合
代码模板 ¶
所有的代码见 union-find-cpp - github
岛屿数量问题 ¶
模板题:
给你一个由
"1"
(陆地)和"0"
(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。
-- 来自 leetcode 200. 岛屿数量
示例:
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
岛屿内的陆地相连,每个岛屿就是一个集合,这是一个求连通分量的问题。
假设输入的方格的大小是 m x n
的,我们通过一个函数来把方格位置 (i,j)
映射到一个数字,以表示并查集中的一个节点标号:
auto f = [=](int i, int j) { return i * n + j; };
也就是 f(i,j)
的值就是代表方格 (i,j)
的节点标号,一共有 m*n
个。
剩下的事情,只需要顺序扫描整个方格,把 1
的格子「合并」到各自归属的集合中去。
由于是自左向右、自上而下扫描,所以只需要合并 左边 和 上边 相邻的格子的集合即可。
最后,合并完成后,输出连通分量即可。
一个细节是,节点总数量初始化为 m*n
的时候,最后答案要刨除 0
的格子的数量。
岛屿数量 - C++ 代码
// 省略 union-find 代码
class Solution {
public:
int numIslands(vector<vector<char>>& g) {
int m = g.size(), n = g[0].size();
UnionFind uf(m * n);
// 映射到节点标号
auto f = [=](int i, int j) { return i * n + j; };
int k0 = 0; // 0 的方格数量,最后要剔除
for (auto i = 0; i < m; i++) {
for (auto j = 0; j < n; j++) {
if (g[i][j] == '1') {
// 上
if (i > 0 && g[i - 1][j] == '1')
uf.Union(f(i, j), f(i - 1, j));
// 左
if (j > 0 && g[i][j - 1] == '1')
uf.Union(f(i, j), f(i, j - 1));
} else
k0++;
}
}
return uf.C() - k0; // C() 返回并查集的连通分量
}
};
(完)
相关文章: 最长连续序列问题
本文原始链接地址: https://writings.sh/post/union-find