版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
概念
Disjoint-Set，也称Union-Find或Disjoint-Set-Union，是一种用于表示不相交集合的数据结构。并查集可用于解决像朋友圈这样的问题，即在一个相互可能为朋友的朋友圈里计算朋友圈的数目，以及判断两个人是否属于同一个朋友圈。
并查集支持以下两种操作：
- 合并：将两个不相交的集合合并为一个。
- 查询：查询两个元素是否在同一个集合中。
初始版
简单的并查集体结构的设计如下：
| 代码块 |
|---|
class DSU { vector<int> parent; public: DSU(int n) : parent(n) { for(int i = 0; i < n; i++) { parent[i] = i; } } int find(int x) { if(parent[x] == x) { return x; } else { return find(parent[x]); } } void merge(int x, int y) { // 将y的parent设置为x的parent parent[find(y)] = parent[find(x)]; } }; |
下面的过程演示了并查集的工作流程：
| draw.io Diagram | ||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
注意，在merge(2, 3)时，需要递归找到2的根结点1，再把3合并到1上。
路径压缩
上面的设计存在一个问题，就是最后形成的并查集树可能层数很高，甚至是一个链，比如下面的操作：
| 代码块 |
|---|
DSU dsu(4);
merge(2, 1);
merge(3, 2);
merge(4, 3); |
生成的树结构如下：
| draw.io Diagram | ||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
随着链越来越长，查询结点的根结点也会越来越耗时。
解决办法就是路径压缩，也就是在每次查询一个结点的根节点时，将沿途结点的父结点全部更新一遍，需要修改的点如下：
| 代码块 |
|---|
int find(int x) {
if(parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
} |
按秩合并
用于确定在合并两个集合时，以哪个集合的根结点作为合并之后的集合的根结点。
正常情况下，合并两个集合（也就合并两颗并查集的树结构）不应该导致树的深度增加，否则查询会更加耗时，所以应该将深度较小的树合并到深度较大的树上，为此，对每个结点额外增加一个rank，表示这个以这个结点为根结点的树的深度，然后在合并时，根据高度进行合并，并更新对应的rank，并查集的优化设计如下：
| 代码块 |
|---|
class DSU { vector<int> parent; vector<int> rank; public: DSU(int n) : parent(n), rank(n) { for(int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } } int find(int x) { if(parent[x] == x) { return x; } else { parent[x] = find(parent[x]); return parent[x]; } } void merge(int x, int y) { int root_x = find(x); int root_y = find(y); if(rank[root_x] <= rank[root_y]) { parent[root_x] = root_y; // 以较高的树作为新的根结点，高度相等，以root_y作为新的根结点 } else { parent[root_y] = root_x; } if(rank[root_x] == rank[root_y] && root_x != root_y) { rank[root_y]++; // 高度相等时，上面的选择以root_y作为根结点，所以rank[root_y]++ } } }; |
并查集应用
547. 省份数量 - 力扣（LeetCode）
若干个城市，有些城市相互连接，所有直接或间接相连的城市构成一个省，求省份数量，直接应用并查集即可。
| 目录 |
|---|