...
- 合并：将两个不相交的集合合并为一个。
- 查询：查询两个元素是否在同一个集合中。
初始版
简单的并查集体结构的设计如下：
| 代码块 |
|---|
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)];
}
}; |
...
注意，在merge(2, 3)时，需要递归找到2的根结点1，再把3合并到1上。
路径压缩
上面的设计存在一个问题，就是最后形成的并查集树可能层数很高，甚至是一个链，比如下面的操作：
| 代码块 |
|---|
DSU dsu(4);
merge(2, 1);
merge(3, 1);
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];
}
} |
按秩合并
用于合并两颗树时，确定以哪个树作为根。