发布于 ,更新于 

并查集

今天讲的最短路啥的感觉有点费劲,先把并查集的东西写了

用途

基本上用来处理 关系
什么是关系?比如一个人和他的表弟是亲戚,亲戚的关系可以人为理清, 但是毒瘤的出题人会给这个人安上 114514 个表弟这些表弟的 1919810 个其他亲戚以及 1145141919810 个其他无关的人,然后问你这个序列里面第 \(a\) 个人和第 \(b\) 个人是不是亲戚,一般的方法显然处理不了,而并查集就是专门用来解决这种东西用的。

实现

“并查集”的操作就是前两个字,即合并与查询。
此处默认以树实现并查集。

合并

合并的操作即把两棵树的根节点连接在一起,文字解释不清楚,但是直接用树结构实现就比较清楚了。

这里我们只需要开一个数组 \(F\) 存储每一个节点的祖先,每次更改 \(i\) 节点的祖先只需要修改 \(F_i\) 的值

比如目前我们有五个点

然后由输入数据可知,13245441 是亲戚,于是我们把 1 设为 5 的祖先来表示他们的关系, 2 4 同理,相当于把这四个集合(或者说树)两两合并

下一步

以及把以 4 为根的这棵树合并到 1 上,连接他们的根节点

这样我们就基本完成了这个集合的初始化,我们只需要再把根节点 1 的祖先设置为自己,来表示它是这棵树的根节点(应该在合并之前初始化每一个结点的祖先为自己,因为图可能会不太清楚所以改到这里了)

代码实现思路就很清楚了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void uni(int x, int y) {
// 查询两个节点所在树的根
xx = find(u);
yy = find(v);

if (xx != yy) f[xx] = yy; //连接根节点
}
/*
...
int main() {
.....
cin >> m >> n; // m 为人数,n 为关系数
int f[m+10], u, v;
int p,q;
memset(f,0,sizeof 0);
for (int i = 1; i <= m; ++i) {
f[i] = i;
}
...
}
*/

查找

假如我们需要查找上一张图里面 2 3 是否是亲戚,如何操作呢?

很容易发现,2 3两个节点在同一棵树中,也就是说我们可以直接查找这两个节点的根节点,如果相同则是亲戚。查找的实现也很简单,直接递归寻找上一级的父亲节点,如果一个节点的祖先是自己,就直接输出这个节点即可

1
2
3
4
5
// 查询 pos 的根
int find(int pos) {
if (f[pos] == pos) return pos; // 边界
return find(father[pos]);
}

优化

由上文可以发现,在并查集中查找一个节点的祖先最坏情况下的时间复杂度是 \(O(h)\) 的(\(h\) 为树的最大深度),那么就可以通过减小最大深度来优化并查集。

按树的大小合并

假如说我们有这样两棵树

现在 1 5两个节点是亲戚,那么把 5 的祖先设为 1 合适还是反过来合适呢?
显然是前者

如果按照前者合并,结果就是

最大深度是 3

如果按照后者合并,最大深度为 4

也就是说,为了让 \(h\) 尽可能地小,需要把深度/体积小的树合并到深度大的树上,作为大深度/体积树的子树

此处定义一个 \(R\) 数组记录以 \(i\) 为根节点的树的最大深度为 \(R_i\)\(R\) 的修改在初始化/添加关系时修改)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void uni(int x, int y) {
int xx = find(x);
int yy = find(y);

if (xx == yy) return; // 在同一棵树中不需要合并

if (r[xx] >= r[yy]) {
f[yy] = xx;
r[xx] = max(r[xx],r[yy]+1); // 可能合并后 y 树深度 +1 大于 x 树最大深度
} else {
f[xx] = yy;
r[yy] = max(r[yy],r[xx]+1);
}
}

路径压缩

以上两棵树显然右侧的树更优,因为它的最大深度更小

并查集的查询方式为“查询根节点”,这意味着我们查询时只需要关注查询最终的根节点,而不用关心查询途中经过的节点,这就是路径压缩的原理。路径压缩即把一个没有连着根的节点(如上图左侧的4 5 6 7),“跳过”所有中间节点,直接把它连到根节点上。
对于上图来说,就是把 4 5 6 7 摘出来连接到 2 3 的父节点上,即 1,于是形成了右图,最大深度从 2 降到了 1。 由于并查集相关的题目中可能初始化之后仍然有需要增删的元素,同时路径压缩也需要耗费时间,所以我们只在查询需要的点时优化。

1
2
3
4
5
6
int find(int x) {
if (x != f[x]) { // 如果 x 不是根节点
f[x] = find(f[x]);
}
return f[x];
}

新的查询函数可以结合上图理解。