并查集学习笔记

· · 算法·理论

\text{Part 1\,\,\,Introduction / 并查集简介}

并查集（Disjoint Set），是一种图论里的数据结构。并查集，顾名思义，可以完成"并"和"查"两种操作。"并"指的是合并两个集合，"查"指的是查询元素所在的集合。

\text{Part 2\,\,\,Example / 例题引入}

题目链接：亲戚

给定 n 个人和 m 对关系，其中一对关系用 M_i,M_j 来表示，指的是 M_i 与 M_j 是亲戚。亲戚的亲戚也是亲戚。 后有 p 次询问，每一次询问 P_i 和 P_j 是否为亲戚。n,m,p \le 5000。

分析：

本题是一道经典的并查集题目。对于每一组亲戚（组内所有人均互相是亲戚关系），我们可以将其看作一棵树，并为其指定一个根。那么，对于两个有亲戚关系的人，它们所在的树必然相等，那么根也就相等。

想到这里我们自然的产生了一种想法：对于第 i 个人，我们用 fa_i 记录这个人所在树的根，那么查询也就好办了：对于两个人 i,j，只需判断 fa_i 与 fa_j 是否相等即可。

对于给定的亲戚操作，如何处理？观察可以发现，当给出 x 和 y 是亲戚后，x 所在的树和 y 所在的树内所有元素均互相具有亲戚关系。那么这两棵树相当于合并成为了一棵树，由于树只能有 1 个根，所以我们选择其中一个根，将其作为另一个根的儿子即可。在合并的过程中，我们需要更新 fa 数组。

以上这个数据结构，我们就将其称为：并查集。

\text{Part 3\,\,\,Implementation / 代码如何实现？}

我们已经有了初步的想法，那么如何实现？又如何在合并过程中维护 fa 数组？

对于这个问题，我们需要实现一个核心函数：\operatorname{find(x)}。这个函数的作用就是找到 x 所在的树的根。这个函数我们可以用递归来实现，伪代码如下：

int find(int x) { //查找树的根
    if(x 为当前树的根) 返回 x;
    else 返回 find(x 的父亲);
}

将其写成 \texttt{C++} 代码就是：

int find(int x) {
    if(fa[x] == x) return x;
    return find(fa[x]);
}

有了这个函数，那么另外两个操作都好办了：对于合并操作 \text{merge}，查找两棵树的根，并将一个树的根作为另一棵树的根的儿子；对于查询操作 \text{ask}，判断两棵树根是否相等即可。

\text{Part 4\,\,\,Std / 示范代码}

以下为根据以上讲解，写出的 P1551 的完整代码。

注意：在初始化时，每个元素都是单独的一棵树，需要将它的根设为自己。

#include <bits/stdc++.h>
using namespace std;
int fa[100005];
int getfa(int x) { //重点 find() 函数
    if(fa[x] == x) return x;
    return getfa(fa[x]);
}
void merge(int x,int y) { //合并
    if(getfa(x) == getfa(y)) return ;
    fa[getfa(x)] = getfa(y);
}
bool issamefa(int x,int y) { //查询
    return getfa(x) == getfa(y);
} 
int main() {
    int n,m,q; cin >> n >> m >> q;
    for(int i = 1;i <= n;i++) fa[i] = i; //初始化
    for(int i = 1;i <= m;i++) {
        int x,y; cin >> x >> y;
        merge(x,y);
    }
    while(q--) {
        int x,y; cin >> x >> y;
        cout << (issamefa(x,y) ? "Yes" : "No") << endl;
    }
    return 0;
}

\text{Part 5\,\,\,Optimize / 优化手段}

\text{Part 5.1\,\,\,Path compression / 路径压缩}

路径压缩是一种常见的并查集优化手段。

考虑如下两张图：

对于元素 2,3,4,5，这两张图是没有变化的。但是，在第一张图中，查询 5 的根需要递归 3 层，而在第二张图中只需要 1 层。由此可见，第二张图在效率上优于第一张图。

那么如何实现呢？很简单：只需将 return find(fa[x]) 改为 return fa[x] = find(fa[x]) 即可。

Q：为什么要这样写呢？

A：因为相当于将自己的父亲直接设为了整棵树的根，自然就达到了我们的目标。

在 n 个结点的树里面，按照原来的方式查询，平均复杂度为 O(\log n) ；最坏情况下，整棵树为一条链，此时复杂度退化为 O(n)。按照优化后的方式查询，只需 O(1) 的复杂度。当 n=10^5 或更大时，这是一个很有效的优化。

\text{*Part 5.2\,\,\,Merge by rank / 按秩合并}

按秩合并是一种在合并时的优化。

这种优化在合并时，会将深度更小的那一棵树合并到更大的那一棵树上，这样不仅能降低时间复杂度，还能尽量减少树的深度。

\text{Part 6\,\,\,Summarize / 总结}

并查集是一种基本操作较为简单，应用广泛的数据结构，使用它可以解决许多与集合合并等相关的问题。

\text{Part 7 Practice / 习题}