并查集 知识点讲解

概念

想象一下，你正在玩一个“找亲戚”的游戏。老师给出了 n 个人，并告诉你若干对“亲戚关系”（比如 A 和 B 是亲戚）。现在来了很多查询，问“X 和 Y 是不是亲戚”？

最暴力的做法是：每次查询时，拿着 X 和 Y，去翻一遍所有已知的亲戚关系，看能不能从 X 走到 Y。如果关系很多，或者查询很多，这种“每次重新跑一遍”的方法会慢到爆炸。

并查集就是为了解决这个问题而生的。它维护了一堆“集合”，每个集合里的元素都是互相连通的（比如都是亲戚）。它只关心“连没连”，不关心具体怎么连的。

触发清单（看到这些信号第一时间想到本知识点）

定义

并查集（Disjoint Set Union, DSU） 用来维护一堆元素的连通关系，支持两种操作：

• find(x)：问“x 属于哪个集合”（找到它的“老大/根”）；
• union(x, y)：把 x 和 y 所在的集合合并成同一个。

最经典的用途：判断“两个人是不是亲戚/连通”“图里加边会不会成环”“最小生成树里选哪些边”。

⚠️ 一句话：并查集就是“动态连通性”的利器——只关心“连没连”，不关心路径怎么走。比每次 BFS 判连通快得多。

手写并查集（带路径压缩 + 按秩合并）：

int fa[100005], rnk[100005];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i, rnk[i] = 0; }

int find(int x) { // 找根 + 路径压缩
 if (fa[x] != x) fa[x] = find(fa[x]); // ⭐ 递归把路径上所有点直接挂到根
 return fa[x];
}
void unite(int x, int y) {
 x = find(x); y = find(y);
 if (x == y) return; // 已在同一集合
 if (rnk[x] < rnk[y]) fa[x] = y; // 小树挂到大树下（按秩合并）
 else { fa[y] = x; if (rnk[x] == rnk[y]) rnk[x]++; }
}
bool same(int x, int y) { return find(x) == find(y); }

三条铁律：

1. find 里必须路径压缩（把 fa[x] = find(fa[x])），否则会退化成链，变慢；

2. unite 前先 find 拿到各自的根，根相同说明已连通；

3. 连通块个数 = 初始 n 减去成功合并的次数（或统计“自己是自己根”的点数）。

技巧速查表（背下来）

例题

例：亲戚问题（P1551 思路）—— 先合并所有已知的亲戚关系，再回答查询。

#include <iostream>
using namespace std;
int fa[5005];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } // 路径压缩
int main() {
 int n, m, q; cin >> n >> m >> q;
 for (int i = 1; i <= n; i++) fa[i] = i; // 初始化：每个人自己一族
 for (int i = 0; i < m; i++) {
 int a, b; cin >> a >> b;
 fa[find(a)] = find(b); // 合并 a、b 所在的族
 }
 while (q--) {
 int a, b; cin >> a >> b;
 cout << (find(a) == find(b) ? "Yes\n" : "No\n"); // 同根 = 亲戚
 }
 return 0;
}

为什么这样对？find(a)==find(b) 表示 a、b 最终指向同一个根，即经过一系列合并后他们在同一个集合里——这正是“亲戚”的传递闭包。路径压缩保证每次查询近乎 O(1)。

下面对照一张图理解“找根 + 路径压缩”：

例题复盘总结

归纳题：亲戚（P1551）

• 共性特征：给定若干“同组”关系，多次查询“是否同组”。本质是维护动态连通性。
• 各自技巧：

- 初始化 fa[i]=i，表示 n 个独立集合。

- 读入每对关系 (a,b) 时，先 find(a), find(b) 拿到根，再令 fa[find(a)] = find(b) 合并。

- 查询时直接比较 find(a) == find(b)。

• 审题模板：看到“连通/同伙/亲戚/能否互相到达” → 并查集；看到“加边/选边” → Kruskal；看到“敌对/不同阵营” → 种类并查集。
• 错误清单：忘记 init；find 没压缩；合并时直接 fa[a]=b 而没先 find 根；统计块数数边而不是数根。

归纳题：村村通（P1536）

• 共性特征：n 个点，m 条边，问最少加几条边能让图连通。本质是数连通块。
• 各自技巧：

- 先对 m 条边建图（邻接表或邻接矩阵）。

- 从任意未访问点开始 BFS/DFS，标记连通块。

- 连通块个数 = n − 成功合并次数（用并查集维护）。

- 答案 = 连通块个数 − 1。

• 审题模板：看到“修路/连整体/最少边” → 并查集 + 计数。
• 错误清单：把连通块数当成答案（应为块数 −1）；忘记处理孤立点；用 BFS 时重复访问导致死循环。

归纳题：家谱（P2814）

• 共性特征：父子关系已知，问两人是否同祖先。本质是维护“同族”关系。
• 各自技巧：

- 父子关系 father[u]=v 等价于 unite(u, v)。

- 多次合并后，查询 find(a)==find(b)。

• 审题模板：看到“父子/合并集合” → 并查集。
• 错误清单：把父子当成单向树而不用并查集；忘记初始化；查询时没先 find。

写法总表

分工说明：触发清单用于“看到题干信号时快速定位知识点”；技巧速查表用于“背下核心代码片段，防止手写出错”；写法总表用于“按功能粒度选择具体模板”。

常见错误

1. find 没压缩：写成 while(fa[x]!=x) x=fa[x]; return x; 不回写，树退化成链，TLE。

2. 合并没先 find 根：直接 fa[x]=y 只把 x 一个点挂到 y，x 的兄弟们没跟着合并，连通关系错。

3. 忘了初始化：fa[i] 不设为 i，初始全 0 或乱值，find 会飞到错误根甚至越界。

4. 用并查集求具体路径：并查集只维护“连通”，不保存路径；要路径用 DFS/BFS。

5. 种类并查集空间开错：敌对关系要把点拆两倍/三倍，数组只开一倍会越界或逻辑错。

6. 统计连通块数错：应数“fa[i]==i”的个数，或 n - 成功合并次数，别数边。

7. 多测不清数组：并查集数组要每轮 init，否则上一组数据的根残留导致 WA。

自测

1. 并查集支持哪两种核心操作？它和 BFS 判连通比，优势在哪？

2. 路径压缩写在 find 的哪一行？为什么它能把复杂度降到近乎 O(1)？

3. unite(x,y) 前为什么要先 find 两个根？直接 fa[x]=y 会怎样？

4. Kruskal 最小生成树怎么用并查集“判环”？为什么要先按边权排序？

5. 怎么统计一个并查集里有几个连通块？

6. 种类并查集（敌人关系）为什么要“把每个点拆两倍空间”？

7. 多组测试数据时，并查集数组最容易漏掉哪一步导致 WA？

举一反三 · 审题流水线

拿到一道题，先别急着写代码，按这个流水线走一遍：

1. 读题抓关键词：有没有“连通”“同伙”“亲戚”“加边”“敌对”“最小生成树”？

2. 定需求：是要判断两点是否连通？要数连通块？要加边判环？还是要维护某种关系？

3. 选工具：只关心连通 → 并查集；要具体路径 → BFS/DFS；要选最便宜的边 → Kruskal + 并查集；有敌对关系 → 种类并查集。

4. 写地基：先写 init 和带压缩的 find，这是所有并查集题的通用模板。

5. 套模板：根据需求，是简单 unite，还是 Kruskal 里的 if(find(u)==find(v)) continue，还是种类并查集的拆点合并。

6. 验边界：n=1 怎么办？多组数据要不要 init？数组开够吗？

练手题

题一：修路连通

有 n 个村庄，编号 1 到 n。最初没有路。接下来有 m 条路要修，每条路连接两个村庄。修完所有路后，问：最少还需要修几条路，才能让所有村庄都连通？

输入格式：

第一行两个整数 n, m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000)。

接下来 m 行，每行两个整数 u, v (1 ≤ u, v ≤ n, u ≠ v)，表示一条路连接 u 和 v。

输出格式：

一个整数，表示最少还需要修的路数。

题二：敌对分组

有 n 个人，编号 1 到 n。已知若干对“敌对关系”：a 和 b 是敌人，不能分到同一组。现在要把所有人分成尽可能少的组，使得每组内部没有敌对关系。问最少需要几组？

输入格式：

第一行两个整数 n, k (1 ≤ n ≤ 100000, 0 ≤ k ≤ 200000)。

接下来 k 行，每行两个整数 a, b (1 ≤ a, b ≤ n, a ≠ b)，表示 a 和 b 是敌人。

输出格式：

一个整数，表示最少需要的组数。