并查集

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

用途

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

实现

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

合并

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

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

比如目前我们有五个点

然后由输入数据可知，1 和 3，2 和 4，5 和 4，4 和 1 是亲戚，于是我们把 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];
}

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