Lesson 0410 · 并查集（Union-Find）

④ 数据结构与算法 — 第 10 课

1. 一个新需求：边加边查

回想 0409 的连通分量：给一张静态的图，外面套一层循环 + DFS，就能数出有几个连通块。

现在把需求改一下：一开始有 n 个孤立的点（1 号到 n 号），接下来给我 m 条指令：

1 x y   ：在 x 和 y 之间连一条边       （把两伙人并成一伙）
2 x y   ：问 x 和 y 现在连通吗         （这两人是一伙的吗）

指令是混着来的：连一下、问一下、再连一下、再问一下。这个场景叫动态连通性。

如果还用 0409 的老办法，每问一次就重跑一遍 DFS，复杂度是 O(m × (n + e))。n = m = 10⁵ 时就是 10¹⁰ 次操作 —— 直接超时。

盯着这个问题看两秒，会发现它天生就是集合的划分：

把每个连通块看成一个集合 → 所有点被分成了若干组
问 "x 和 y 连通吗"        → 问 "x 和 y 在同一个集合里吗"
连一条边 x-y              → 把 x 所在的集合和 y 所在的集合并起来

"在同一个集合里"这种关系有三个明显的性质：自己和自己当然同组；x 和 y 同组则 y 和 x 同组；x 跟 y 同组、y 跟 z 同组，则 x 跟 z 同组。

数学上管这叫等价关系，而"等价关系"和"集合的划分"是一一对应的。所以我们要维护的东西，本质就是一堆集合，支持两个动作：合并（unite）和查询（find）。这个数据结构就叫并查集。

2. 朴素想法：给每个点发一个"队伍编号"

最直接的做法：给每个点记一个编号 team[x]，表示它属于第几队。一开始大家各成一队，team[x] = x。

合并两队的时候，把其中一队里所有人的编号统统改掉：

int team[100005];

for (int i = 1; i <= n; i++) team[i] = i;    // 各成一队

// 把 x 和 y 所在的队伍并成一队
int tx = team[x], ty = team[y];
if (tx != ty)
    for (int i = 1; i <= n; i++)             // ★ 挨个改一遍
        if (team[i] == tx) team[i] = ty;

查询是 O(1)：team[x] == team[y]。合并是 O(n)：一整队人都要动。

别急着说"O(n) 也还行"。下面这组是真的跑出来的数字（同样的机器、同样的编译选项），用最坏情况"链式合并"（1 并 2，再把 1-2 并 3，再把 1-2-3 并 4……）：

看第二列：n 每翻一倍，时间翻 4 倍 —— 这就是 O(n²) 的典型长相。

为什么这么慢？因为每次合并都要把整队人挨个改一遍。

可是……我们真的在乎"每个队员记的编号是几"吗？

不在乎。 我们唯一在乎的是"谁和谁是一伙的"。这个"挨个改一遍"从头到尾都是白干的活。

3. 关键洞察：不记"队伍编号"，只记"我指向谁"

换个记法。每个点只记一个信息：我指向谁，也就是 fa[x] = x 的父亲。初始时所有点都指向自己：fa[x] = x。

这样一来，一堆点加上这些"指针"就组成了一片森林：

        fa[3] = 3   ← 根（自己指向自己）
        /     \
    fa[1] = 3   fa[2] = 3

         fa[7] = 7   ← 另一棵树的根
        /
    fa[5] = 7

树上两个定义：

• 根：fa[x] == x 的点。根的编号就当作这个集合的代表元
• 集合 = 一棵树：同一棵树上的所有点，就是一伙的

于是查询和合并各一句话：

• 查询：从 x 出发，沿 fa 一路往上爬，爬到根。两个点连通 ⟺ 它们爬到的是同一个根
• 合并：把一棵树的根，挂到另一棵树的根下面。一条赋值语句搞定

这就是并查集的全部思想。之所以叫 fa，是因为它是"儿子指向父亲"（father）—— 注意方向和普通二叉树是反的。

3.1 两个函数，先写最朴素的版本

int fa[100005];

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i;   // 一开始各自是根
}

// 找 x 所在树的根
int find(int x) {
    while (fa[x] != x) x = fa[x];   // 只要不是根，就往上爬一层
    return x;
}

// 合并 x 和 y 所在的两个集合
void unite(int x, int y) {
    fa[find(x)] = find(y);          // 让 x 的根认 y 的根当爸爸
}

对比一下朴素写法和并查集：

合并从 O(n) 掉到了 O(1) —— 代价是查询从 O(1) 变成了 O(树高)。这笔买卖划算吗？取决于树高会不会失控。

4. 雷在哪里：树被串成了一条长链

上面那个 unite 有个大问题。看这串操作：

unite(1, 2);   // fa[1] = 2
unite(2, 3);   // fa[2] = 3
unite(3, 4);   // fa[3] = 4
unite(4, 5);   // fa[4] = 5
...
unite(n-1, n); // fa[n-1] = n

每一条新的边都挂在链条的一端，结果树变成了一条直线：

1 → 2 → 3 → 4 → 5 → ... → n        （n 是根）

这时候 find(1) 要爬 n 层。如果题目反复问最深的那个点，查询就退化成 O(n)，整体又回到 O(n²)。

4.1 手推：这条链是一层一层长出来的

取 n = 6，照上面那串 unite 走五步，把 fa[1] 到 fa[6] 整个数组抄下来：

每一步只改一个格子（fa[新根] = 老根），而且"唯一的新点"总是挂到"当前最深的地方"，所以链越拉越长。n 个点就是 n−1 层。

实测（n = 100000 的一条长链，然后问 20000 次 find(n)）：

一模一样的树、一模一样的查询，只因为 find 里多写了一句话，3236 毫秒变成 0 毫秒。

4.2 优化一：路径压缩（path compression）

想法很朴素：既然爬这一趟已经知道根是谁了，那顺手把路上所有点的父亲都直接改成根。下次再问，就是一步到位。

int find(int x) {
    if (fa[x] == x) return x;          // 已经是根了
    return fa[x] = find(fa[x]);        // ★ 爬到根，顺手把 fa[x] 改成根，再把根交出去
}

把 return fa[x] = find(fa[x]); 拆开看，它其实做了三件事：

1. 先算右边：find(fa[x]) —— 递归往上爬到根，拿到根 r
2. 再把 fa[x] 改写成 r（这一步就是"路径压缩"）
3. 最后把 r 交出去（赋值的值就是右边的值，正好返回）

拿 4.1 那条 6 个点的链，跑一次 find(1)，前后对比：

注意第三行：压缩不会让这一次变快，它只改 fa，该爬的路一步不少。赚的是后面每一次 —— 这就是"均摊"的含义。

4.3 优化二：按大小合并（union by size）

路径压缩是"查询时补救"。还有一招是"合并时就别把树弄坏"：

合并的时候，把小的那棵树挂到大的那棵树下面。

先想清楚为什么。上面那条长链是怎么形成的？因为每次都是「新来的点被挂到了大树的根下面」，或者更糟——「大树被挂到了孤零零的一个点下面」，树就一层层长高了。

如果规定"小的挂到大的"，一个点最深会被重新挂多少次？每被挂一次，它所在的树至少翻倍。所以最多被挂 log n 次 —— 树高永远是 O(log n)。

需要一个数组记每棵树的大小（只在根上有意义）：

vector<int> sz;                  // size，每棵树有几个点
sz.assign(n + 1, 1);             // 一开始每个点自成一棵大小为 1 的树

void unite(int a, int b) {
    a = find(a);                 // ★ 必须先各自找到根
    b = find(b);
    if (a == b) return;          // 本来就是一伙的，什么都不用做

    if (sz[a] < sz[b]) swap(a, b);   // 让 a 是较大的那棵树的根
    fa[b] = a;                       // 小的挂到大的下面
    sz[a] += sz[b];                  // 合并后的大小要更新（只更新根）
}

4.4 复杂度：快到基本等于常数

两个优化一起用，并查集的均摊复杂度是 O(α(n))。α 是阿克曼函数的反函数，它长得极其慢 —— n 大到 10¹⁸ 时，α(n) 也只有 4 左右。

说人话：一次合并或者查询，基本就是常数时间。

实测（P3367，满规模）：

最后一行最能说明问题：点数从 20 万涨到 2000 万（100 倍），时间只从 11ms 变成 73ms。 因为并查集的耗时几乎只跟操作次数 m 有关，和 n 基本脱钩。

5. 完整模板（这个要背下来）

#include <iostream>
#include <vector>
using namespace std;

vector<int> fa, sz;

void init(int n) {
    fa.resize(n + 1);
    sz.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) fa[i] = i;
}

int find(int x) {                          // 递归版 + 路径压缩
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;                    // 已经在一起，直接返回
    if (sz[a] < sz[b]) swap(a, b);         // 小的挂到大的下面
    fa[b] = a;
    sz[a] += sz[b];
}

就这 20 行，是后面 Kruskal 最小生成树、种类并查集、带权并查集的共同地基。

5.1 备选：迭代版 find

递归版很干净，但有个隐患：递归深度 = 树高。模板里有路径压缩所以树很矮，一般不会出事；但如果你以后手抖漏了压缩，或者遇到特别恶毒的数据，就可能爆栈。迭代版不靠递归，分两趟走：

int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];      // 第一趟：一路爬到根，记下根是 r

    while (fa[x] != r) {               // 第二趟：把路上每个点直接接到根上
        int nxt = fa[x];                // 先存下原来的父亲，不然一改就丢了
        fa[x] = r;
        x = nxt;
    }
    return r;
}

两趟都是 O(树高)，做的是同一件事。知道有这条路存在就行，平时写递归版。

6. 三个必须会用的套路

6.1 判连通 —— 最常见的用法

if (find(x) == find(y)) cout << "Y" << endl;
else                    cout << "N" << endl;

6.2 判环 —— 无向图加了这条边会不会成环

一条一条边地加，每加一条之前先检查：

// 加边 (u, v) 之前
if (find(u) == find(v))
    cout << "这条边会构成环！" << endl;   // u、v 本来就连通，再加就成了环
else
    unite(u, v);                        // 本来不通，加完还是一棵树

道理很简单：如果 u、v 之间本来就已经有路径了，那再补上 u-v 这条边，这段路径加上这条边就围成了一个环。反过来，如果本来不连通，加上这条边只是把两棵树连成一棵，不会产生环。

已验证：4000 组随机图和暴力 DFS 判环的结果逐组一致。

顺带得到一个推论：n 个点的无向图，如果一直加边而又不想成环，最多只能加 n − 1 条边。（这就是"树"的定义：n 个点、n−1 条边、连通。）

6.3 增量地数连通块个数

0409 数连通分量要跑一遍 DFS。用了并查集，可以边合并边数：

int comps = n;               // 一开始每个点自成一伙，共 n 伙

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;      // 本来就在一伙，伙数不变
    if (sz[a] < sz[b]) swap(a, b);
    fa[b] = a;
    sz[a] += sz[b];
    comps--;                 // ★ 成功合并了两伙，伙数减一
}

comps 任何时候都等于"当前的连通块个数"。已验证与"重新数一遍"的结果一致。

这个技巧很实用：以后遇到"每次加边后输出连通块数目"，就不需要每次都重跑 DFS。

7. 综合应用：P3958 奶酪

来看一道把并查集用出花的题。

题意：一块高 h 的奶酪，里面有 n 个球形空洞，第 i 个的球心在 (x_i, y_i, z_i)，半径 r（所有空洞半径相同）。老鼠在奶酪底面（z = 0）上，想到达顶面（z = h）。它可以沿着空洞的内部移动，两个空洞只要相交或者相切就能互相通过。问：能不能从底走到顶？

这题看起来是三维几何，其实核心只有一句话：能不能通过 = 连通不连通。

先把几何条件翻译成判断式：

然后造两个虚拟节点：0 号 = 底面，n + 1 号 = 顶面。这俩不是真实的空洞，只是为了让我们能问出那句 find(底面) == find(顶面)。接着把所有"相通"的关系都 unite 起来：

if (z[i] <= r)       unite(i, 0);        // 这个洞碰到奶酪底面
if (h - z[i] <= r)   unite(i, n + 1);    // 这个洞碰到奶酪顶面

// 任意两个洞：相交就合并
if (dx*dx + dy*dy + dz*dz <= (2*r)*(2*r))
    unite(i, j);

最后答案就是一句话：

cout << (find(0) == find(n + 1) ? "Yes" : "No") << endl;

完整代码（已验证，样例输出 Yes / No / Yes）：

#include <iostream>
#include <vector>
using namespace std;

int fa[1005];

int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); }
void unite(int a, int b) { a = find(a); b = find(b); if (a != b) fa[a] = b; }

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long n, h, r;
        cin >> n >> h >> r;

        int BOT = 0, TOP = n + 1;                  // 两个虚拟节点
        for (int i = 0; i <= n + 1; i++) fa[i] = i;

        vector<long long> x(n + 1), y(n + 1), z(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> x[i] >> y[i] >> z[i];
            if (z[i] <= r)         unite(i, BOT);   // 碰到底面
            if (h - z[i] <= r)     unite(i, TOP);   // 碰到顶面
        }

        long long d2 = 4 * r * r;                   // (2r)²，必须 long long
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++) {
                long long dx = x[i] - x[j];
                long long dy = y[i] - y[j];
                long long dz = z[i] - z[j];
                if (dx * dx + dy * dy + dz * dz <= d2) unite(i, j);
            }

        cout << (find(BOT) == find(TOP) ? "Yes" : "No") << endl;
    }
    return 0;
}

注意这里我没有用 sz / 按大小合并 —— n 只有 1000，路径压缩已经绰绰有余。做题时按需上优化，不是每道题都要写满。

8. 坑点清单

• 初始化漏了 / 多组数据没清空 —— fa[i] = i 且 sz[i] = 1，T 组数据要整组重来，这是最常见的 WA
• find 忘了路径压缩 —— fa[x] = find(fa[x]) 里那个赋值是性能的命根子，漏了就 TLE
• 拿 fa[x] == fa[y] 当判断 —— 父亲不是代表元，必须 find(x) == find(y)
• unite 不先 find、丢了 if (a == b) return; —— 参数可能不是根；同集合还挂，纯粹有害；大小只更新根
• 该 long long 的地方写了 int —— 坐标平方、边权和、计数这三类最常溢出
• 指望并查集拆边 —— 它只进不退；真要拆边得用可撤销并查集（按秩合并 + 栈记录，不能用路径压缩）或离线倒着做。另外路径压缩会改写 fa，别拿它兼职存别的信息

9. 小测

10. 动手练习

三题是同一套模板的三级台阶。按顺序做，做完并查集就算入门了。

1. P3367 【模板】并查集 —— 直接套模板。Z = 1 合并，Z = 2 查询输出 Y / N。规模 n ≤ 2×10⁵、m ≤ 10⁶，一定要加快读（ios::sync_with_stdio(false); cin.tie(nullptr);），不然光输入就够呛
2. P1551 亲戚 —— 一模一样的操作，只是换了故事：m 条亲戚关系、p 次询问，输出 Yes / No。重点：这一题就是上一题换个皮，别被故事绕进去
3. P3958 奶酪 —— 综合应用，考的是"能不能把几何关系翻译成连通关系"，外加虚拟节点的技巧。重点：long long 的溢出坑 + 不开根号

卡住时的自查顺序

1. fa[i] = i 初始化了吗？多组数据重来了吗？
2. find 里的路径压缩写了吗（fa[x] = find(fa[x])）？
3. 比较用的是 find(x) == find(y)，还是不小心写成了 fa[x] == fa[y]？
4. unite 开头 a = find(a); b = find(b); 写了吗？if (a == b) return; 有吗？
5. 有没有会溢出的乘法该换 long long？
6. 还是不行就把代码贴过来，我们一起看。

选做（有挑战）：如果觉得三题都太顺，可以试试把 P3958 改成"用 DFS 从底面灌水"再写一遍，然后对比两种写法 —— 体会一下同一个问题，换个数据结构，代码量差多少。

本课小结

• 并查集解决"动态连通性"：一边加边一边问"这俩连通吗"
• 核心结构：森林。fa[x] = 父亲，fa[x] == x 的点是根，根 = 集合的代表元
• 两个函数：find 一路爬到根；unite 把一个根挂到另一个根下面
• 路径压缩：fa[x] = find(fa[x])，爬到根时顺手拍平路径（3236ms → 0ms 的那一句）
• 按大小合并：小的挂到大的下面，树高永远 O(log n)
• 两个优化一起上，均摊 O(α(n))，α(n) ≤ 4 —— 基本就是常数
• 三个套路：判连通（find(x) == find(y)）· 判环（加边前两端已连通就成环）· 增量数连通块（comps--）
• 虚拟节点技巧：给"底面""顶面"这种抽象条件也发一个编号，让它们参与并查集（P3958）
• 并查集不支持删除和拆边；要拆边得用可撤销并查集或离线倒做