如果你刷算法题或者准备面试大概率遇到过这么一类题给你一堆元素告诉你哪些属于同一个集合然后反复问两个元素是否连通。这类问题最经典的数据结构就是并查集。我这次想把并查集、种类并查集、带权并查集放在一起讲透从朴素实现到优化从模板题到经典题把里面的坑和套路全部摊开说清楚。这篇内容适合刚学数据结构的人也适合准备考研、面试、算法竞赛的人。我会用大量实际代码和推导过程帮你把三种并查集的“为什么”讲明白而不只是丢给你模板背。1. 从零理解并查集这个结构到底在解决什么问题1.1 一个生活化的例子先想一个场景班里有 n 个学生一开始每个人都不认识其他人。老师不停告诉你“甲和乙认识”“丙和丁认识”这里的“认识”具有传递性——甲认识乙乙认识丙那甲和丙也就算间接认识。现在老师问你任意两个人之间到底认不认识如果不做任何预处理每次询问都得顺着关系链走一遍最坏情况是 O(n) 的。当 n 到几十万询问几十万次时直接爆炸。并查集干的就是这件事它能在近乎 O(1) 的复杂度内回答“两个元素是否在同一个集合”并且能快速把两个集合合并成一个。上面这个场景里每个“认识圈”就是一个集合每次告诉你“甲和乙认识”就是合并两个集合每次询问“甲乙认不认识”就是查询两个元素是否在同一个集合。1.2 两个核心操作一个数组并查集的底层存储极简单就一个数组 parentparent[x] 表示 x 的父节点。初始化时让每个元素的父节点指向自己代表每个元素独立成一个集合for (int i 1; i n; i) parent[i] i;核心操作只有两个find(x)找到 x 所在集合的根节点。根节点的特征是 parent[x] x。union(x, y)把 x 和 y 所在的两个集合合并本质是把一个根挂到另一个根下面。// 朴素实现 int find(int x) { while (parent[x] ! x) x parent[x]; return x; } void unionSet(int x, int y) { int fx find(x), fy find(y); if (fx ! fy) parent[fx] fy; // 让一个根成为另一个根的父节点 }这里有个很容易忽略的点合并时我们操作的是两个集合的根而不是 x 和 y 本身。很多人第一次写容易直接 parent[x] fy这会把 x 从它原来的集合里“拽”出来后面 find 就乱掉了。正确姿势永远是先 find 拿到根再挂根。1.3 复杂度为什么不是 O(n)而是接近 O(1)朴素实现有一个问题如果合并时每次都把深度大的挂到深度小的下面树会退化成一条链。比如依次合并 (1,2)、(2,3)、(3,4)构造出来就是 1 - 2 - 3 - 4 的形状find(1) 要一路走到底复杂度 O(n)。后来有人发现find 的时候顺便把路径上经过的节点直接挂到根下面树的深度就会被拉平。这个优化叫路径压缩。再配合按秩合并并查集的均摊复杂度会被压到 O(α(n))其中 α(n) 是阿克曼函数的反函数。这个函数增长极其缓慢n 相当于整个宇宙的原子数时α(n) 也不会超过 5所以你可以直接把它当作常数来看。这也是为什么并查集在工程和竞赛里如此常用——简单、快、省空间。2. 基础版到优化版路径压缩与按秩合并2.1 路径压缩让树变得更扁平路径压缩的核心思想很简单既然我们只关心元素属于哪个集合不关心树的具体形态那 find 的时候把沿途节点全部直接指向根就好了。// 递归版 int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } // 非递归版防止递归过深 int find(int x) { int root x; while (parent[root] ! root) root parent[root]; while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }递归版在绝大多数场景下够用因为路径压缩后树高会变得很小。但如果你在极端环境下栈空间紧张或者树的形态一开始就特别深非递归版更稳。我写竞赛代码时一半用递归版一半用非递归版看心情关键是两种写法都要熟练。路径压缩最容易被问到的面试题是路径压缩之后树的形态变了会不会影响并查集的正确性答案是不会。因为并查集只维护“集合关系”不维护树的任何额外信息。你只需要保证同一集合的根一致至于树长什么样无所谓。2.2 按秩合并让树尽量平衡只看路径压缩理论上均摊复杂度已经很优秀了但有一种极端情况你先 union 了 n/2 次构建出一棵深度很大的树第一次 find 就会把这棵树压平但在此之前所有 union 操作都要沿着深路径走总复杂度可能退化到 O(n log n) 级别。为了更稳我们引入按秩合并。这里的“秩”一般指树的深度上界也可以指集合大小。合并时让秩小的树挂到秩大的树下面避免深度无脑增加int parent[MAXN], rank[MAXN]; void unionSet(int x, int y) { int fx find(x), fy find(y); if (fx fy) return; if (rank[fx] rank[fy]) swap(fx, fy); parent[fy] fx; if (rank[fx] rank[fy]) rank[fx]; }注意rank 记录的是“未压缩前的深度上界”。路径压缩可能会让实际深度变小但我们不需要因此去更新 rank因为按秩合并只用秩的相对大小来决定挂载方向秩偏大一点不影响正确性CLRS 里面把这种优化叫做 union by rank。2.3 两种优化到底要不要一起上严格来说只有路径压缩没有按秩合并时间复杂度是 O((mn) log n) 量级虽然实际几乎碰不到退化只有按秩合并没有路径压缩复杂度是 O(log n)。两者都用才是 O(α(n))。那竞赛和工程里怎么选我的习惯是普通连通性问题路径压缩 按秩合并都写上模板越稳越好。种类并查集、带权并查集合并方向往往决定了权值怎么传如果随意按秩合并会让权值更新公式变得很麻烦所以这类题目我一般只做路径压缩固定合并方向然后靠路径压缩保证效率。实测下来在 n 是 10^5 级别时只做路径压缩完全够用。3. 种类并查集三倍空间维护多类关系3.1 从“吃与被吃”的循环关系说起基础并查集只能表达“同类”关系但很多实际问题里元素之间不止同类关系还有敌对、捕食这类带有方向性的关系。经典的例子是食物链问题有 n 个动物分成 A、B、C 三类A 吃 BB 吃 CC 吃 A。给你若干条信息“x 和 y 同类”或者“x 吃 y”信息可能有一小部分是假的需要你统计假信息的数量。这里的关键约束是三类动物形成一个循环x 和 y 的关系不只是“相同/不同”而是有三种可能同类、x 吃 y、y 吃 x。基础并查集没法直接表达三态关系。种类并查集也叫扩展域并查集的思路是给每个元素开 k 个“域”k 是关系类别数。对于食物链开 3 倍数组对每个动物 ii 表示动物 i 属于 A 类i n 表示动物 i 属于 B 类i 2n 表示动物 i 属于 C 类这样就把“i 属于某一类”这个状态拆成了三个互斥的节点。合并时我们实际上是在表达“如果 i 属于 A那么 j 属于 B”这类条件命题。3.2 食物链里的关系推导当输入“x 和 y 同类”时逻辑是x 属于 Ay 就必须属于 Ax 属于 By 就必须属于 Bx 属于 Cy 就必须属于 C。所以合并三对节点union(x, y)union(x n, y n)union(x 2n, y 2n)当输入“x 吃 y”时因为 A 吃 B、B 吃 C、C 吃 A所以如果 x 是 Ay 就是 B合并 (x, y n)如果 x 是 By 就是 C合并 (x n, y 2n)如果 x 是 Cy 就是 A合并 (x 2n, y)判断矛盾永远在合并之前做。以“x 和 y 同类”为例如果在合并前就发现 find(x) find(y n)说明根据之前的信息x 和 y 已经被判定为吃的关系那现在说它们同类就是假的这条信息不能合并答案计数加一。同理“x 吃 y”需要检查 find(x) find(y)说明之前已经判定同类和 find(x) find(y 2n)说明之前已经判定 y 吃 x。3.3 食物链完整代码种类并查集版#include bits/stdc.h using namespace std; const int MAXN 150005; // 3 * 50000 余量 int fa[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unionSet(int a, int b) { fa[find(a)] find(b); } bool same(int a, int b) { return find(a) find(b); } int main() { int n, k; scanf(%d%d, n, k); for (int i 1; i 3 * n; i) fa[i] i; int ans 0; while (k--) { int d, x, y; scanf(%d%d%d, d, x, y); if (x n || y n) { ans; continue; } if (d 1) { // x 和 y 同类 if (same(x, y n) || same(x, y 2 * n)) ans; else { unionSet(x, y); unionSet(x n, y n); unionSet(x 2 * n, y 2 * n); } } else { // x 吃 y if (same(x, y) || same(x, y 2 * n)) ans; else { unionSet(x, y n); unionSet(x n, y 2 * n); unionSet(x 2 * n, y); } } } printf(%d\n, ans); return 0; }关于此题三个容易踩的坑数组要开到 3 * n 1不然下标越界尤其 n 取到 50000 时开 50005 会直接 RE。每次合并前必须把三个映射关系都做完整漏一对后面判断就会错。输入量可能很大用 scanf 或者关闭 C 流同步不要裸用 cin 跑大数据实测会慢很多。3.4 种类并查集还能用在什么地方只要关系是可分类的、可传递的并且类别之间存在循环制约种类并查集就是首选。最典型的是“朋友 vs 敌人”问题开两倍空间i 表示 i 在集合 Ai n 表示 i 在集合 B合并时把敌人关系表达为“i 和 j 不在同一集合”。这个思路在 NOIP 2010 的《关押罪犯》里非常好用我后面第 5 章会再写一道完整题。种类并查集的局限性也很明显它需要事先知道总的类别数 k并且把数组乘 k。如果 k 很大或者关系不是简单的循环类别就得考虑带权并查集了。4. 带权并查集用向量偏移直接维护关系4.1 权值的本质是“到父节点的关系”带权并查集不一定要开 k 倍空间而是在每个节点上额外维护一个权值 rel[x]表示 x 与 parent[x] 的关系。还是以食物链为例我们定义 rel[x] 为 x 到其父节点 parent[x] 的关系0x 与 parent[x] 同类1x 吃 parent[x]2x 被 parent[x] 吃即 parent[x] 吃 x注意这个定义是有方向的。很多资料里方向反着定义公式就会差一个符号所以看别人代码时一定要先搞清楚他的方向约定不然照抄必挂。有了方向定义我们就可以用一个统一公式表达关系传递x 与它的祖父节点的关系等于 x 与父节点的关系加上父节点与祖父节点的关系然后对 3 取模rel[x] (rel[x] rel[parent[x]]) % 34.2 find 时怎么更新权值路径压缩时x 的父节点会从原来的 parent[x] 直接变成根节点那么 rel[x] 也必须同步更新成“x 和根节点的关系”。公式就是上面那行。但实现时有个特别容易踩的坑递归调用 find 之后parent[x] 已经变了如果你直接写 rel[x] (rel[x] rel[parent[x]]) % 3这里面的 parent[x] 已经是根rel[根] 0加了个寂寞。正确写法是先保存旧的父节点int find(int x) { if (parent[x] ! x) { int oldParent parent[x]; // 先保存因为下一步 parent[x] 会被覆盖 parent[x] find(oldParent); // 递归压缩 rel[x] (rel[x] rel[oldParent]) % 3; } return parent[x]; }这是带权并查集最容易写错的地方我见过不少人卡在这里好几天。你要是写完发现权值越更新越乱九成是这个原因。4.3 union 时的权值计算合并两个集合时我们要设置两个根之间的权值。假设要把 x 所在集合合并到 y 所在集合即 parent[fx] fy并且我们知道的信息是x 与 y 的关系为 d0 同类1 x 吃 y2 x 被 y 吃。现在需要求 rel[fx]也就是 fx 与 fy 的关系。利用关系传递把 x 到 y 的路径拆成四段x 到 fx权值是 rel[x]find 之后x 直接挂在 fx 下fx 到 fy权值是 rel[fx]这是我们要设的值fy 到 y注意 rel[y] 是 y 到 fy 的关系反方向取反即 (3 - rel[y]) % 3关系传递公式d (rel[x] rel[fx] (3 - rel[y])) % 3解出 rel[fx]rel[fx] (d - rel[x] - (3 - rel[y]) 3) % 3 (rel[y] - rel[x] d 3) % 3这个公式就是代码里那句parent[fx] fy; rel[fx] (rel[y] - rel[x] d 3) % 3;为什么最后要 3 再 %3因为 C 的取模运算对负数会得到负数比如 -2 % 3 -2而我们希望得到 1。先 3 再 %3 是处理这类问题最保险的方式。4.4 判断两点关系同一根之下的关系比较当 find(x) 和 find(y) 相等时说明 x、y 已经在同一个集合里它们处于同一个根之下这时可以直接比较它们与根的关系来判断彼此关系。x 与根的关系是 rel[x]y 与根的关系是 rel[y]。x 与 y 的关系rel(x, y) (rel[x] - rel[y] 3) % 3结果为 0同类结果为 1x 吃 y结果为 2x 被 y 吃所以在食物链里如果题目输入的是 d 1同类我们先把 d-- 变成 0d 2x 吃 y变成 1。这样判断逻辑统一成当两个点已经连通时如果 (rel[x] - rel[y] 3) % 3 ! d说明这条信息与之前的信息矛盾。完整代码食物链带权并查集版#include bits/stdc.h using namespace std; const int MAXN 50005; int parent[MAXN], rel[MAXN]; int n, k; int find(int x) { if (parent[x] ! x) { int old parent[x]; parent[x] find(old); rel[x] (rel[x] rel[old]) % 3; } return parent[x]; } int main() { scanf(%d%d, n, k); for (int i 1; i n; i) parent[i] i; int ans 0; while (k--) { int d, x, y; scanf(%d%d%d, d, x, y); if (x n || y n) { ans; continue; } d--; // 0 同类1 x吃y2 x被y吃 int fx find(x), fy find(y); if (fx fy) { if ((rel[x] - rel[y] 3) % 3 ! d) ans; } else { parent[fx] fy; rel[fx] (rel[y] - rel[x] d 3) % 3; } } printf(%d\n, ans); return 0; }这段代码和前面种类并查集版本的输出结果完全一致。我建议你两个代码都跑一遍 POJ 1182然后交叉验证这个题是理解种类并查集和带权并查集关系的绝佳材料。4.5 权值不一定是模 3 的循环带权并查集的“权”不只是食物链里的三态关系它还可以是普通的差值、距离、区间和等。比如 HDU 3038 的区间统计题给你若干个 [l, r] 区间和等于 s 的描述让你统计多少条描述是假的。这类题里rel[x] 表示的是“x 到父节点的差值”路径压缩时权值直接相加合并时用减法求两个区间之间的差值。没有模运算但思路完全一样先 find 判断两个端点是否已经连通连通就能通过差值判断矛盾不连通就按差值合并。所以你要记住带权并查集的本质在并查集树上维护一条“向量”信息任何两个节点之间的关系都可以通过它们各自到根的关系计算出来。至于这条信息是模几的、是加法还是乘法都是具体的权值定义问题。5. 实战对比从题目特征到完整代码5.1 怎么识别该用哪种并查集面试和竞赛里遇到并查集题目第一步不是写代码而是判断它属于哪一类。我整理了下面的对照表基本可以覆盖大部分题型题目特征推荐方案经典题只问“是否连通”“是否同一个集合”基础并查集LeetCode 547、200、684、Kruskal 判环关系是“朋友/敌人”“同类/不同类”且关系可传递种类并查集扩展域2倍或k倍空间LeetCode 990、NOIP 2010 关押罪犯关系有方向吃/被吃/同类且关系循环带权并查集mod kPOJ 1182 食物链权值是差值、区间和等具体数值带权并查集权值为差值HDU 3038、洛谷 P2294有个小技巧如果关系种类只有两类比如“朋友/敌人”用两倍扩展域写起来非常直观如果关系种类有三类且循环优先考虑带权并查集代码更短空间也更省。5.2 关押罪犯一道特别适合练习种类并查集的题NOIP 2010 的《关押罪犯》是种类并查集的经典题。题意大概是这样有 n 个罪犯m 对罪犯之间有仇恨值现在要把他们分到两座监狱同一座监狱里的两个罪犯如果有仇恨就会爆发冲突。问怎么分配能让“爆发冲突的最大仇恨值”最小。思路很直接把所有仇恨按值从大到小排序尽量让仇恨值大的两个人分到不同监狱。用两倍扩展域的并查集维护“同一个监狱”的关系i 表示罪犯 i 在监狱 Ai n 表示罪犯 i 在监狱 B每处理一对仇恨 (a, b)先检查 find(a) 是否等于 find(b)。如果已经相等说明无论如何这两个人都会被分到同一个监狱因为之前的合并关系已经强制推导出这一点那当前的仇恨值就是答案直接输出。否则把 a 和 b 分到不同监狱unionSet(a, b n); // a 在 A 监狱b 在 B 监狱 unionSet(b, a n); // b 在 A 监狱a 在 B 监狱这两次合并必须都做。很多人只做了第一句后面判断就漏掉了一半的约束。完整核心代码#include bits/stdc.h using namespace std; const int MAXN 40005; int fa[MAXN]; struct Edge { int a, b, w; bool operator (const Edge other) const { return w other.w; } } edges[100005]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unionSet(int a, int b) { fa[find(a)] find(b); } int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i 2 * n; i) fa[i] i; for (int i 0; i m; i) { scanf(%d%d%d, edges[i].a, edges[i].b, edges[i].w); } sort(edges, edges m); // 仇恨值从大到小 for (int i 0; i m; i) { int a edges[i].a, b edges[i].b; if (find(a) find(b)) { printf(%d\n, edges[i].w); return 0; } unionSet(a, b n); unionSet(b, a n); } printf(0\n); return 0; }这题的核心思想是“贪心 并查集”。从大到小处理冲突直到某一对冲突无法避免那它就是答案。这个贪心是成立的原理类似“最大生成树”里的 Kruskal 流程其实 Kruskal 本身就是在用并查集做贪心很多“最大值最小”的题都能用这个套路。5.3 扩展带权并查集做区间问题顺手再说一个我自己很喜欢的例子HDU 3038。题目给了很多形如“区间 [l, r] 的和是 s”的描述判断多少条描述和前面的冲突。这种题的关键是把前缀和思想搬到并查集上令 sum[x] 表示从某个起点到 x 的前缀和那么 [l, r] 的和 s 就等价于 sum[r] - sum[l-1] s。我们把 l-1 和 r 放进并查集rel[r] 表示 r 到父节点的差值。如果 l-1 和 r 已经连通就能用它们分别到根的距离算出实际区间和和 s 对比就知道冲突。如果不连通就按差值方向合并。区间问题的权值是普通整数没有模运算但 find 和 union 的本质和食物链完全一致。这也是我反复强调“带权并查集的核心是向量偏移”的原因——换一层皮思路完全复用。6. 常见问题与避坑清单6.1 高频错误整理我从自己刷题和帮别人 debug 的经历里把并查集相关的高频错误都整理成了一张表错误现象根本原因解决办法find 之后 rel 越变越乱更新 rel 时用了已经被覆盖的 parent[x]先保存 oldParent再递归最后更新 rel合并后某些点关系不对合并时没有先 find直接操作元素本身永远先 find 拿到根再操作根取模结果出现负数C 的 % 对负数取模还是负数一律写成 (x MOD) % MOD种类并查集数组越界数组只开了 n 的大小开到 k * n 1k 等于扩展域数量多组测试数据 WA只初始化一次 parent每组输入前都重新 init判断矛盾 / 合并顺序反了先 merge 再检查冲突一定要先 find 检查再决定是否 mergecin 读大数据超时输入量大cin 同步开销高用 scanf 或 ios::sync_with_stdio(false)6.2 我的调试习惯并查集这种题错误往往不是报编译错误而是答案悄悄错几个数。所以调试时要有技巧。我的习惯是第一写一个 debug 函数把 parent 和 rel 数组直接打印出来在小样例上手动跟踪每一轮 find 和 union 后的状态验证 rel 的更新是否符合预期。这个方法对带权并查集尤其有效因为 rel 的推导一旦错了多跑几轮就能看出数值规律不对。第二食物链这个题用种类并查集和带权并查集各写一遍然后对拍。两个代码思路完全不同如果答案一致基本能说明两个方向的推导都对如果答案不一致就缩小范围排查是哪一步的关系映射写错了。第三注意数据范围。很多并查集题目 n 都是 10^5 甚至 10^6 级别递归版 find 虽然有路径压缩但极端情况下还是可能出现爆栈风险。如果你在线上环境遇到栈溢出改成非递归版就好。6.3 面试和竞赛里怎么练如果是为了面试重点放在基础并查集上LeetCode 的 547、200、684、721、990 都值得做一遍。面试官更喜欢问“并查集的应用场景”和“优化原理”你要能说清楚路径压缩和按秩合并各自解决了什么问题。如果是为了竞赛或者考研种类并查集和带权并查集是必须掌握的进阶内容。我建议的练习顺序是先做基础并查集模板题再做食物链POJ 1182这两道通过后做关押罪犯NOIP 2010增加实战感最后挑战 HDU 3038 理解带权并查集的区间应用。按这个顺序学下来大部分并查集题目都不会再让你头疼。我个人在实际操作中的体会是并查集这个数据结构最反直觉的地方不是代码难写而是“关系”的抽象。你只要先把元素之间的关系画清楚确定好权值方向代码几乎就是公式套用。我写带权并查集时每次都会先在草稿纸上画出 x、y、fx、fy 四条关系边再推导公式几乎没出过错。你也试试这个方法比自己硬记公式要可靠得多。