算法·理论：并查集

· · 算法·理论

1. 并查集的起源

‌并查集（Disjoint Set 或者 Union-Find Set）的起源可以追溯到一九六四年，由 Bernard A. Galler 和 Michael J. Fischer 提出‌‌。

并查集是一种树型的数据结构，主要用于处理不相交集合的合并及查询问题。不相交集合指的是交集为空集的一些集合。并查集通过合并和查询操作，可以有效地维护集合的连通性信息，广泛应用于图论、动态连通性等问题中。

2. 引入并查集

我们可以通过以个小问题来引入并查集。

某场编程竞赛有很多学生来参赛，其中一些同学来自同一学校。现在我们已知其中 M 对学生来自同一学校（具体哪所未知），请你回答一系列询问：每个询问都需要回答某 2 位同学是不是来自同一学校。

这个问题可以抽象成无向图上的连通问题，利用 BFS 或 DFS 可以在 O(N+M) 时间内回答一个询问。或者 O(N+M) 的预处理之后 O(1) 时间回答一个询问。

但是，如果同校信息的收集和询问是实时交错进行的，怎么办？

思路：集合。我们可以认为一开始每个人都单独属于一个自己的集合。当知道 x 与 y 同校时，我们把包含 x 的集合与包含 y 的集合合并。询问 2 人是否同校等价于询问是否属于一个集合。

初始 {张三} {李四} {王五} {赵六}
张三王五同校 {张三，王五} {李四} {赵六}
李四赵六同校 {张三，王五} {李四，赵六}
张三李四同校 {张三，王五，李四，赵六}

关于上述集合方法的实现，就是并查集！

3. 并查集的操作及原理

1° 并查集的操作

代码详见：

// fa 数组记录每个节点的父亲
int find(int x) {
    if (fa[x] == x) return x;
    return find(fa[x]);
}

为了方便查找代表元，开始时请将全部的 fa[i] 赋值为 i。

代码详见：

void merge(int x, int y) {
    int rtx = find(x), rty = find(y);
    if (rtx == rty) return;
    fa[x] = y;
}

4. 并查集的优化

虽说并查集是由很多个树组成的，但是树的形态各异。

当我们考虑到查询代表元的时间复杂度时，不但想到时间复杂度就是这棵树的高度。

万一，这棵树形成了一条链呢？时间复杂度将从大约 O(\log_{}{n}) 变到大约 O(n) 了。如果这样，那还用并查集干什么？为了避免形成一条链，我们给出以下两种方案：

代码详见：

// 这里的“秩”是按照节点数少的树合并到节点数多的树上
// 这里的 sz 数组是记录一每个节点为根的节点个数
void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) {
        if (sz[x] > sz[y]) swap(x, y);
        fa[x]=y; sz[y]+=sz[x];
    }
}

一开始请将全部的 sz[i] 赋值为 1。

5. 并查集的时间复杂度

6. 带权并查集

个人认为还是比较难。

带权并查集是在普通并查集的基础上增加了权值的概念，用于记录节点到根节点的距离。在合并操作中，更新权值以反映新结构下的距离。具体实现时，可以通过新建数组来存储合并集合间的距离关系，简化计算‌。

1° 带权并查集的查询操作

提出问题：求出节点 x 比节点 y 大多少？

代码详见：

// 这里没有加路径压缩
int find(int x, int &d) {
    d = 0;
    while (x != fa[x]) {
        d += w[x];
        x = fa[x];
    }
    return x;
}

2° 带权并查集的合并操作

现在给出了条件：节点 x 比节点 y 的值大 z。

那又如何计算出新的边权呢？我们可以列一个方程。

假设两个节点属于不同的两棵树，将 x 属于的那棵树合并到 y 属于的那棵树上。设 x 到他的根节点边权之和为 dx，y 到他的根节点边权之和为 dy，x 的根节点到 y 的根节点的权值为 w，则有方程：

dy - (w + dx) = z\\ dy - w - dx = z\\ w = dy - dx - z\\

（这里的 z 是条件中设定的）

代码详见：

// 这里加了按秩合并
void merge(int x, int y, int d) {
    int dx, dy;
    x = find(x, dx); y = find(y, dy);
    if (x == y) return;
    if (sz[x] > sz[y]) {
        swap(x, y);
        swap(dx, dy);
        d = -d;
    }
    fa[x] = y;
    sz[y] += sz[x];
    dis[x] = dy - dx - d;
}

7. 扩展域并查集

扩展域并查集最适合干的就是：给出了两个元素的关系，但都不能确定的题目。就比如说：已知小黄和小绿性别不同，有小黄男小绿女和小黄女小绿男两种情况，不能确定是哪一种。

我们还是通过题目来深入了解扩展域并查集吧。

题目：P1525 [NOIP2010 提高组] 关押罪犯
这是一道扩展域并查集的板题。

一开始贪心的结论就不说了，就是要有顺序地处理某两个罪犯不在同一个监狱。

输入就会变成这样：

4 6
1 2 28351
3 4 12884
1 3 6618
2 3 3512
1 4 2534
2 4 1805

看第一个，意思为 1 号和 2 号不能再同一个监狱，我们把监狱规定成 A，B 两个。

此时我们有 1A、1B、2A、2B、3A、3B、4A、4B 这 8 种情况。

既然1号和2号不能再同一个监狱，我们就把 1A 和 2B 连一条边，同理，要把 1B 和 2A 连一条边。

以此类推，直到 2 号和 3 号不能在同一个监狱连完边后，发现 2A 和 2B 等在同一个监狱，此时矛盾，所以答案就是矛盾时的影响力，即 3512。

再提一嘴，这道题还可以不用并查集来做。先二分，每次二分到的值进行黑白染色，判断是否有奇环，时间复杂度 O(m \log_{}{m})，也能通过。

这就是扩展域并查集的大致实现与思路。由于扩展域并查集的使用方法跟普通的并查集十分相似，所以代码就不放了。

8. 尾言

关于并查集的知识和内容都差不多写全了。这篇关于并查集的文章不仅仅巩固了我的并查集知识，还为大家提供了学习的资料，请管理员通过，谢谢阅读！