不少人刚开始学并查集时都觉得这玩意儿也太简单了——维护一堆元素属于哪个集合查一查根合并一下完事。可一旦题目换个马甲比如告诉你“A吃B、B吃C、C吃A”或者给你一串“区间内1的个数是奇数还是偶数”的条件让你找矛盾普通并查集就明显不够用了。这时候就要上一层楼接触到种类并查集和带权并查集。这篇文章我打算把这三层一次讲透从底层原理到代码实现再到调试技巧实操性拉满。无论你是准备考研数据结构、应付期末考试还是刷 LeetCode、搞算法竞赛认真看完应该都能有收获。1. 并查集解决的到底是个什么问题1.1 动态连通性一个比想象中更常见的需求并查集的原始模型非常朴素有 n 个元素初始时每个元素单独形成一个集合。支持两种操作把两个元素所在的集合合并成一个以及查询两个元素是否在同一个集合里。这类问题在算法里有个专门的名字叫动态连通性。我举个生活中的例子。假设你在运营一个兴趣社团系统用户 A 加入了羽毛球群羽毛球群和跑步群合并了跑步群里又有 B。你随时要回答“A 和 B 当前是不是在同一个群体系里”。如果用户量只有几十个你用数组给每个人打集合编号每次合并重新遍历一遍也能忍。可一旦数据量到了十万、百万级合并一次就遍历所有人操作次数一多直接崩盘。这还没完。并查集在算法题里几乎是无处不在的配角。最小生成树 Kruskal 算法要判断“加上这条边会不会成环”本质就是查询两个点的连通性离线处理区间合并问题要先按某种顺序把相邻位置合并起来图论里统计连通分量个数也常直接套并查集。包括工程里做依赖分组、网络设备连通性检测很多场景其实都能抽象成“合并集合 查询关系”。所以如果你只把并查集当成“教材里的一个数据结构”去背它的价值你就只吃到了十分之一。真正该理解的是它为什么能在近似 O(1) 的时间里完成这些操作以及它后续演化出的“种类”和“带权”版本能表达多么丰富的关系模型。1.2 为什么用树来组织而不是给每个人重写编号先说说最常见的错误直觉给每个集合记录一个编号再维护一个数组belong[x] 集合编号。查询两个元素是否同集合只需要比较编号O(1)快得很。问题出在合并要把一个集合的所有元素的belong改掉就必须遍历这个集合里每一个元素。哪怕你聪明地选择把小的集合合并进大的集合最坏情况下整体复杂度依然可以达到 O(n log n) 级别而且编码复杂度很高多个集合反复合并时会非常痛苦。并查集换了个思路每个集合不存“编号”而是一棵有向的树根节点就是集合的代表元素。每个节点都存一个父指针fa[x]指向它的上一级。合并两个集合时我只需要找到两个集合的根节点然后把其中一个根节点的父指针指向另一个根节点——这就是一次 O(1) 的指针操作。查询时沿着父指针一层层向上走直到根节点就能确定代表元素。这个思想用一句话总结就是合并动作本身不折腾下层节点只折腾代表节点。就像两个班级合并不需要让全班所有人都互相握手两个班长碰个头全校的“归属关系”就确定了。后续任何人想知道自己属于哪个班沿着“学生→班长→年级负责人”这条链一路向上找就行。当然如果树的形态退化成一条链每次查询都要 O(n) 地往上走用并查集反而比暴力还慢。所以就有了路径压缩和按秩合并这两个优化这也正是并查集真正封神的原因。2. 手写一个趁手的并查集代码与优化细节2.1 最简版本先能用再谈优化先直接给出一份最朴素的并查集实现你们感受一下代码量const int N 100010; int fa[N]; void init(int n) { for (int i 1; i n; i) fa[i] i; } int find(int x) { if (fa[x] x) return x; return find(fa[x]); } void merge(int x, int y) { int fx find(x), fy find(y); if (fx ! fy) fa[fx] fy; } bool query(int x, int y) { return find(x) find(y); }核心就两个函数。find递归向上找根merge把一棵树的根挂到另一棵树的根上。query就是find的比较。这里的fa[i] i初始化很重要它表示每个节点在一开始都是自己的根也就是“自成一派”。这个版本在数据量小、或者操作次数少时完全够用。但注意如果不断把链式结构合并比如依次 merge(1,2)、merge(2,3)、merge(3,4)……这棵树会越来越像一根甘蔗find(4)要往前跳 4 次find(100000)要跳十万次复杂度直接爆炸。我当年第一次在竞赛里用未优化的并查集就被一组精心构造的数据卡到怀疑人生。从那以后我写并查集基本默认带上下面这两个优化。2.2 路径压缩和按秩合并哪个更重要所谓路径压缩就是在find返回根节点的过程中顺手把路径上所有经过的节点直接指向根。这样以后查询这些节点时一步就能到根无需再层层往上爬。int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); }注意这行fa[x] find(fa[x])它不仅仅是递归调用还做了一个赋值操作——把 x 的父指针直接指向递归返回的根节点。这就是路径压缩的关键。所谓按秩合并指的是合并时尽量把“矮树”接到“高树”下面避免树长高。实操中通常用集合大小来替代树高也就是常说的按大小合并int fa[N], sz[N]; void init(int n) { for (int i 1; i n; i) { fa[i] i; sz[i] 1; } } int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } void merge(int x, int y) { int fx find(x), fy find(y); if (fx fy) return; if (sz[fx] sz[fy]) swap(fx, fy); fa[fx] fy; sz[fy] sz[fx]; }这里sz[x]表示以 x 为根的集合里有多少个元素。合并时如果发现sz[fx] sz[fy]就先交换保证总是把小的集合挂到大的集合上。这样树的深度增长是 O(log n) 级别的。那是不是两个优化必须同时上理论分析告诉我们单独使用路径压缩时总复杂度是 O(m log n)单独使用按秩合并时总复杂度也是 O(m log n)。只有两者同时使用均摊单次操作复杂度才达到反阿克曼函数 O(α(n))这是一个增长极其缓慢的函数可以认为小于 5。实际做题时我基本总会一起用。因为它们各自只多几行代码带来的收益却是指数级的。但面试或者考试里如果只让你描述“并查集的基本操作”别忘了把“路径压缩”和“按秩合并”挂到嘴边这是两个标志性的优化点。这里还有一个容易被忽略的细节递归的find在极端情况下会爆栈。虽然路径压缩会让树高很矮但如果在递归过程中调用非常深仍有风险。比赛里可以用非递归写法比如循环先找到根再沿着路径做第二次循环赋值。不过我自己的习惯是先用递归版只有当题目数据规模达到百万级以上才会换成非递归版本。3. 种类并查集当集合里不止一种关系3.1 朋友的敌人是不是你的敌人普通并查集答不了普通并查集只能表达“在同一个集合”或“不在同一个集合”这种二元关系。但现实世界里的关系远没这么简单。经典例子就是“敌人的敌人是朋友”。假设 A 和 B 是敌人B 和 C 是敌人那你不能简单地把 A 合并到 B再把 C 合并到 B因为 A 和 C 在逻辑上应该是一伙的可普通并查集里它们各自和 B 的关系是没法区分的。竞赛里还有个流传极广的题目原型——“食物链”三种动物循环捕食A 吃 BB 吃 CC 吃 A。现在给你一串描述有的说“X 和 Y 是同类”有的说“X 吃 Y”让你判断哪些话和前面已知条件是矛盾的。这种题目如果你只维护一份并查集完全无从下手因为你需要的不是“是否同类”这一个信息而是“同类、猎物、天敌”三种角色关系。这时候有两个主流解法一个叫扩展域并查集一个叫带权并查集。我先讲更直观的扩展域。3.2 扩展域写法把一个点拆成多个角色扩展域的思想很朴素既然每个元素有多个角色那我就把每个角色都当成一个独立的点放进并查集里。以上面的“食物链”为例对第 i 个动物我开出三个点i表示“i 自己”这个角色i n表示“i 的猎物”这个角色i 2n表示“i 的天敌”这个角色。这样总节点数是 3n。初始时所有角色都各自成集合。接下来每来一条信息我不是只合并“两个元素”而是合并“相关的角色集合”。比如“X 和 Y 是同类”那意味着X 自己的集合和 Y 自己合并X 的猎物集合和 Y 的猎物合并X 的天敌集合和 Y 的天敌合并。也就是把三个角色完全对齐。“X 吃 Y”怎么合并这句话等价于X 的猎物是 YX 是 Y 的天敌同时 X 的天敌是 Y 的猎物因为食物链是一个环A吃B、B吃C、C吃A所以天敌的猎物之间也有关联。所以要做三次合并void unite(int x, int y) { int fx find(x), fy find(y); if (fx ! fy) fa[fx] fy; } void same(int x, int y) { // 声明x和y是同类 unite(x, y); unite(x n, y n); unite(x 2 * n, y 2 * n); } void eat(int x, int y) { // 声明x吃y unite(x n, y); // x的猎物是y unite(x, y 2 * n); // x是y的天敌 unite(x 2 * n, y n); // x的天敌是y的猎物 }判断矛盾时也很直观。如果某句话声称“X 和 Y 是同类”但现有的并查集里已经有了find(X n) find(Y)说明 X 的猎物是 Y也就是 X 吃 Y或者find(X 2 * n) find(Y)说明 X 的天敌是 Y也就是 Y 吃 X那这句话就是假的。如果某句话声称“X 吃 Y”但现有的并查集里已经能推出find(X) find(Y)同类或者find(X 2 * n) find(Y)说明 X 的天敌是 Y也就是 Y 吃 X那它也是假的。这个思路的优势是逻辑清晰不太需要推导复杂的数学公式懂并查集基本操作的人很快能上手。缺点是空间变大了如果有 k 种角色就要开 k*n 的数组。但一般 k 都很小比如 2、3所以完全能接受。3.3 开两倍数组的典型场景朋友与敌人不只是三倍数组很多“二分关系”题目只需要开两倍数组。比如最常见的“朋友与敌人”问题A 和 B 是敌人B 和 C 是敌人问 A 和 C 是不是朋友。这种题的处理方式是i表示 i 所在的“朋友阵营”i n表示 i 所在的“敌人阵营”。当 X 和 Y 是朋友时合并X与Y合并Xn与Yn当 X 和 Y 是敌人时合并X与Yn合并Xn与Y。很多初学者会好奇为什么敌人关系要交叉合并因为如果 X 和 Y 是敌人那么 X 的朋友就是 Y 的敌人X 的敌人就是 Y 的朋友。这个交叉合并把“敌人的敌人是朋友”这条隐式规则编码进了并查集。一旦后续发现find(X) find(Y)说明朋友阵营重合那就矛盾了。所以种类并查集的本质是用“多开几个集合”的方式把原本只能表达“正反”两类关系的问题扩展为能够表达“正、反、中立”、“猎物、天敌、同类”等多角色关系。当你遇到“对于任意两个元素它们之间可能有多种互斥关系”的题目时第一时间就该想到扩展域。4. 带权并查集从“连通”升级到“距离”4.1 边上的权值到底在表达什么如果扩展域的核心是“多开几个集合”那带权并查集的核心就是“给每条边加一个数值”。这个数值可以表示相对关系、相对距离、奇偶差异等完全取决于题目语义。举个最简单的例子现在有一排位置每个位置放一个数字。告诉你一系列条件比如“区间 [l, r] 内所有数字的和是奇数”或者“A 比 B 的权重大 3 个单位”。你不仅要判断这些条件是否矛盾还要在某些情况下计算两个点之间的差值。这时候普通并查集的fa[x]只有一个父节点信息远远不够用。带权并查集的做法是在fa[x]之上再维护一个d[x]表示节点 x 到父节点fa[x]的“距离”或“关系值”在模 M 的意义下取值。这里的 M 取决于关系种类数或者问题的模数。比如食物链问题中0 表示同类1 表示吃2 表示被吃M3奇偶性问题中0 表示偶数1 表示奇数M2。当你查询根节点并做路径压缩时d[x]要一路累加上去最终变成 x 到根节点的权值。这个过程需要格外小心因为递归本身容易把顺序搞乱。4.2 路径压缩时的权值更新写法先看最常用的递归写法int fa[N], d[N]; // d[x] 表示 x 到 fa[x] 的权值模 mod int find(int x) { if (fa[x] x) return x; int root find(fa[x]); // 先递归找到根 d[x] (d[x] d[fa[x]]) % mod; // 此时 fa[x] 已经被递归地压缩为根了 fa[x] root; return fa[x]; }为什么这里d[x] d[fa[x]]是对的因为递归调用find(fa[x])之后fa[x]这个位置已经被更新成了整个集合的根同时d[fa[x]]也更新成了原 fa[x] 到新根的权值。所以 x 到根的权值 原来的 d[x]x 到旧父亲 旧父亲到根的权值 d[fa[x]]。最后赋值fa[x] root完成路径压缩。更保险的写法是先保存旧父节点int find(int x) { if (fa[x] x) return x; int old fa[x]; int root find(old); d[x] (d[x] d[old]) % mod; fa[x] root; return root; }两种写法本质一样第二种对新手更友好不容易在递归过程中被“奇怪的顺序”绕晕。4.3 合并时的权值推导别硬背公式要会推合并操作是带权并查集最容易出错的地方。假设现在有一条信息“x 和 y 的关系值为 r”仍然在模 M 意义下具体 r 的含义由题目定义。x 所在集合的根是fxy 所在集合的根是fy。我要把fx挂到fy下面那么新的d[fx]应该等于多少这里不能靠默写得自己推一遍。先明确符号d[x]表示 x 到fx的权值d[y]表示 y 到fy的权值题目给出的条件是 x 到 y 的关系值为 r。合并后fa[fx] fy我们需要的是d[fx]也就是 fx 到 fy 的权值。从 fx 出发沿着d[fx] d[x]这条路径能走到 x从 x 再到 y 需要关系 r从 y 再到 fy 需要d[y]。合并后整条路径应该自洽也就是说d[fx] d[x] r d[y]在模 M 意义下移项得到d[fx] d[y] - d[x] - r但不同题目的 r 方向定义不同有的定义是“x 到 y 的关系”有的是“y 到 x 的关系”所以代码里可能出现d[fx] (d[y] - d[x] r) % mod这样的式子也可能出现减号。关键是别背公式每次做新题时先画一条路径自己推一遍方向。实现时为了防止负数通常会这样写void merge(int x, int y, int r) { int fx find(x), fy find(y); if (fx fy) return; fa[fx] fy; d[fx] ((d[y] - d[x] r) % mod mod) % mod; }注意这行后面先取模再加mod再取模确保结果落在[0, mod-1]区间。4.4 实战理解奇偶性问题如何用带权并查集这类题的经典问法给你一个 01 序列然后给出一串条件每个条件说“区间 [l, r] 内 1 的个数是奇数还是偶数”让你判断最早在第几条条件处出现矛盾。思路是维护前缀和数组pre[i]区间 [l, r] 内的奇偶性等于pre[r] xor pre[l-1]。我们不需要知道前缀和的具体数值只需要知道任意两个前缀和的奇偶关系是否自洽。于是把pre[l-1]和pre[r]当成两个节点用带权并查集维护它们的异或值也就是模 2 意义下的差值。如果条件说区间内是“偶数个 1”则pre[l-1]和pre[r]奇偶性相同关系值 r 0如果条件说区间内是“奇数个 1”则pre[l-1]和pre[r]奇偶性不同关系值 r 1。每次拿到新条件先查询fx find(l-1)和fy find(r)。如果已经在同一个集合里就检查当前已知的d[l-1]和d[r]计算出的奇偶关系是否和题目给的一致不一致就是矛盾。如果不在同一个集合就执行带权合并。这种问题如果不提前想到“前缀和奇偶性”这个转化哪怕你背熟了带权并查集代码也想不到要这么用。所以带权并查集真正难的往往不是代码而是把题目条件抽象成“两个点的权值差”这个建模过程。多看几道典型题慢慢就会建立条件反射。5. 常见问题、调试技巧与适用场景速查5.1 那些年我踩过的并查集坑先列几个新手极容易踩的坑每一条我都亲眼见过或者自己踩过。第一初始化漏了。fa[i] i没写全或者下标从 0 开始但循环只到了 n-1查询时直接访问到没初始化的垃圾值。这是最基础但也最高发的错误没有之一。第二递归 find 爆栈。路径压缩并不是银弹如果并查集合并时没按秩合并又连续做了很多次合并递归深度仍然可能很大。比赛里我见过有人因为递归爆栈导致 RE而不是 WA。大数据量时建议还是写循环版。第三合并时根选反了。比如merge(x, y)里写成fa[y] x虽然对于普通并查集查询连通性影响不大但在带权并查集里方向一旦反了所有d的推导全部颠倒最后出一堆莫名其妙的结果。第四模运算负数处理。带权并查集的d[fx]计算时d[y] - d[x] r可能是负数。如果直接对负数取模不同语言对负数的处理不一样很容易出问题。统一写成((val) % mod mod) % mod。第五路径压缩时d[x]更新顺序错。新手容易写成d[x] d[fa[x]]但此时fa[x]已经是经过递归压缩后的根如果没先用一个临时变量保存旧父节点最后算出来的权值会差很远。5.2 一个很容易复制的调试套路调试并查集问题最直接的方法写一个小的暴力版本然后随机数据对拍。具体做法是维护一份朴素的、不含路径压缩的并查集或者直接在每次操作后用 DFS 遍历整个集合看连通关系再和优化版的答案对比。对拍数据要覆盖随机合并、随机查询、随机矛盾条件。一旦发现两边答案不一致立刻把出错的那组输入打出来手动模拟。如果只是单纯调试带权并查集很多人会盯着代码看半天也看不出所以然。我更喜欢在每个关键操作后打印fa数组和d数组比对样例的每一步。写一个简单的debug()函数输出所有节点的父节点和权值观察在哪一步开始和预期不符问题通常就一目了然。另一种有效手段是拿一道题的两个版本互相验证扩展域版本和带权版本各写一遍对拍验证这样不仅验证了代码正确性还能加深理解。我就曾经用食物链这题把扩展域和带权写法都写了一遍从此对带权并查集的公式推导有了一种“肌肉记忆”。5.3 哪些场景用普通、种类还是带权整理一个速查表方便做题时快速定位该用哪一型。场景类型推荐方案说明连通性判断、Kruskal 判环、连通块计数普通并查集路径压缩 按秩合并朋友与敌人、奇偶阵营、二分关系判断种类并查集扩展域至少开 2 倍数组食物链、三角捕食、多角色关系种类并查集或带权并查集扩展域开 3 倍数组带权用模 3区间奇偶性、前缀和差值判断带权并查集模 2转化为前缀和节点相对排名、相对差值关系带权并查集模根据题目求和/差值推导区间和校验、并查集维护偏移量带权并查集模可灵活选择前缀和思想这张表只是一个大方向实际题目经常要混合使用。比如某些题用种类并查集描述角色但每个角色内部还带权值那就要组合。5.4 复杂度与学习路径建议普通并查集在同时使用路径压缩和按秩合并后单次操作均摊时间复杂度为 O(α(n))这里 α(n) 是反阿克曼函数增长速度比 log n 还要慢得多在实际数据范围内完全可以当成常数看待。种类并查集因为多开了 k 倍数组空间是 O(kn)时间仍然是 O(α(kn))。带权并查集只在每次 find 时多做几次加法和取模时间依然稳定在接近常数的水平。学习路径上我不建议一上来就盯着黑皮书里的各种证明看。正确的顺序应该是先把普通并查集背熟然后用“食物链”这题分别用扩展域和带权写法各做一遍再做两道“奇偶游戏”和“带权排名”的题最后回头看原理。你会发现底色其实都是同一个东西在“合并集合”之上表达“关系”关系的表达要么靠多开集合要么靠边权。6. 写在最后一点个人的体会写并查集这几年我最大的感受是它是一个“易学难精”的典型。入门只需要 10 分钟但真正在题目里用对、用活需要积累很多模型。比如看到区间条件就想到前缀和节点看到多种角色关系就想到扩展域或带权这种条件反射不是靠背模板能建立的必须靠实战喂出来。我自己刷题时有个习惯每遇到一种新的“关系判定类”模型就会研究它能不能用并查集建模。就算某道题正解是线段树或者平衡树我也会先想想并查集版本的思路哪怕最后不用这个思考过程也让我对并查集的边界有了更清晰的认知。话说回来面试和考试里并查集的出现频率非常高性价比确实拉满。如果你正被这东西绕得头大不妨先把最基础的手写版跑通再用食物链练手我觉得收获会来得很快。
并查集进阶：从路径压缩到种类并查集与带权并查集全解析
不少人刚开始学并查集时都觉得这玩意儿也太简单了——维护一堆元素属于哪个集合查一查根合并一下完事。可一旦题目换个马甲比如告诉你“A吃B、B吃C、C吃A”或者给你一串“区间内1的个数是奇数还是偶数”的条件让你找矛盾普通并查集就明显不够用了。这时候就要上一层楼接触到种类并查集和带权并查集。这篇文章我打算把这三层一次讲透从底层原理到代码实现再到调试技巧实操性拉满。无论你是准备考研数据结构、应付期末考试还是刷 LeetCode、搞算法竞赛认真看完应该都能有收获。1. 并查集解决的到底是个什么问题1.1 动态连通性一个比想象中更常见的需求并查集的原始模型非常朴素有 n 个元素初始时每个元素单独形成一个集合。支持两种操作把两个元素所在的集合合并成一个以及查询两个元素是否在同一个集合里。这类问题在算法里有个专门的名字叫动态连通性。我举个生活中的例子。假设你在运营一个兴趣社团系统用户 A 加入了羽毛球群羽毛球群和跑步群合并了跑步群里又有 B。你随时要回答“A 和 B 当前是不是在同一个群体系里”。如果用户量只有几十个你用数组给每个人打集合编号每次合并重新遍历一遍也能忍。可一旦数据量到了十万、百万级合并一次就遍历所有人操作次数一多直接崩盘。这还没完。并查集在算法题里几乎是无处不在的配角。最小生成树 Kruskal 算法要判断“加上这条边会不会成环”本质就是查询两个点的连通性离线处理区间合并问题要先按某种顺序把相邻位置合并起来图论里统计连通分量个数也常直接套并查集。包括工程里做依赖分组、网络设备连通性检测很多场景其实都能抽象成“合并集合 查询关系”。所以如果你只把并查集当成“教材里的一个数据结构”去背它的价值你就只吃到了十分之一。真正该理解的是它为什么能在近似 O(1) 的时间里完成这些操作以及它后续演化出的“种类”和“带权”版本能表达多么丰富的关系模型。1.2 为什么用树来组织而不是给每个人重写编号先说说最常见的错误直觉给每个集合记录一个编号再维护一个数组belong[x] 集合编号。查询两个元素是否同集合只需要比较编号O(1)快得很。问题出在合并要把一个集合的所有元素的belong改掉就必须遍历这个集合里每一个元素。哪怕你聪明地选择把小的集合合并进大的集合最坏情况下整体复杂度依然可以达到 O(n log n) 级别而且编码复杂度很高多个集合反复合并时会非常痛苦。并查集换了个思路每个集合不存“编号”而是一棵有向的树根节点就是集合的代表元素。每个节点都存一个父指针fa[x]指向它的上一级。合并两个集合时我只需要找到两个集合的根节点然后把其中一个根节点的父指针指向另一个根节点——这就是一次 O(1) 的指针操作。查询时沿着父指针一层层向上走直到根节点就能确定代表元素。这个思想用一句话总结就是合并动作本身不折腾下层节点只折腾代表节点。就像两个班级合并不需要让全班所有人都互相握手两个班长碰个头全校的“归属关系”就确定了。后续任何人想知道自己属于哪个班沿着“学生→班长→年级负责人”这条链一路向上找就行。当然如果树的形态退化成一条链每次查询都要 O(n) 地往上走用并查集反而比暴力还慢。所以就有了路径压缩和按秩合并这两个优化这也正是并查集真正封神的原因。2. 手写一个趁手的并查集代码与优化细节2.1 最简版本先能用再谈优化先直接给出一份最朴素的并查集实现你们感受一下代码量const int N 100010; int fa[N]; void init(int n) { for (int i 1; i n; i) fa[i] i; } int find(int x) { if (fa[x] x) return x; return find(fa[x]); } void merge(int x, int y) { int fx find(x), fy find(y); if (fx ! fy) fa[fx] fy; } bool query(int x, int y) { return find(x) find(y); }核心就两个函数。find递归向上找根merge把一棵树的根挂到另一棵树的根上。query就是find的比较。这里的fa[i] i初始化很重要它表示每个节点在一开始都是自己的根也就是“自成一派”。这个版本在数据量小、或者操作次数少时完全够用。但注意如果不断把链式结构合并比如依次 merge(1,2)、merge(2,3)、merge(3,4)……这棵树会越来越像一根甘蔗find(4)要往前跳 4 次find(100000)要跳十万次复杂度直接爆炸。我当年第一次在竞赛里用未优化的并查集就被一组精心构造的数据卡到怀疑人生。从那以后我写并查集基本默认带上下面这两个优化。2.2 路径压缩和按秩合并哪个更重要所谓路径压缩就是在find返回根节点的过程中顺手把路径上所有经过的节点直接指向根。这样以后查询这些节点时一步就能到根无需再层层往上爬。int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); }注意这行fa[x] find(fa[x])它不仅仅是递归调用还做了一个赋值操作——把 x 的父指针直接指向递归返回的根节点。这就是路径压缩的关键。所谓按秩合并指的是合并时尽量把“矮树”接到“高树”下面避免树长高。实操中通常用集合大小来替代树高也就是常说的按大小合并int fa[N], sz[N]; void init(int n) { for (int i 1; i n; i) { fa[i] i; sz[i] 1; } } int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } void merge(int x, int y) { int fx find(x), fy find(y); if (fx fy) return; if (sz[fx] sz[fy]) swap(fx, fy); fa[fx] fy; sz[fy] sz[fx]; }这里sz[x]表示以 x 为根的集合里有多少个元素。合并时如果发现sz[fx] sz[fy]就先交换保证总是把小的集合挂到大的集合上。这样树的深度增长是 O(log n) 级别的。那是不是两个优化必须同时上理论分析告诉我们单独使用路径压缩时总复杂度是 O(m log n)单独使用按秩合并时总复杂度也是 O(m log n)。只有两者同时使用均摊单次操作复杂度才达到反阿克曼函数 O(α(n))这是一个增长极其缓慢的函数可以认为小于 5。实际做题时我基本总会一起用。因为它们各自只多几行代码带来的收益却是指数级的。但面试或者考试里如果只让你描述“并查集的基本操作”别忘了把“路径压缩”和“按秩合并”挂到嘴边这是两个标志性的优化点。这里还有一个容易被忽略的细节递归的find在极端情况下会爆栈。虽然路径压缩会让树高很矮但如果在递归过程中调用非常深仍有风险。比赛里可以用非递归写法比如循环先找到根再沿着路径做第二次循环赋值。不过我自己的习惯是先用递归版只有当题目数据规模达到百万级以上才会换成非递归版本。3. 种类并查集当集合里不止一种关系3.1 朋友的敌人是不是你的敌人普通并查集答不了普通并查集只能表达“在同一个集合”或“不在同一个集合”这种二元关系。但现实世界里的关系远没这么简单。经典例子就是“敌人的敌人是朋友”。假设 A 和 B 是敌人B 和 C 是敌人那你不能简单地把 A 合并到 B再把 C 合并到 B因为 A 和 C 在逻辑上应该是一伙的可普通并查集里它们各自和 B 的关系是没法区分的。竞赛里还有个流传极广的题目原型——“食物链”三种动物循环捕食A 吃 BB 吃 CC 吃 A。现在给你一串描述有的说“X 和 Y 是同类”有的说“X 吃 Y”让你判断哪些话和前面已知条件是矛盾的。这种题目如果你只维护一份并查集完全无从下手因为你需要的不是“是否同类”这一个信息而是“同类、猎物、天敌”三种角色关系。这时候有两个主流解法一个叫扩展域并查集一个叫带权并查集。我先讲更直观的扩展域。3.2 扩展域写法把一个点拆成多个角色扩展域的思想很朴素既然每个元素有多个角色那我就把每个角色都当成一个独立的点放进并查集里。以上面的“食物链”为例对第 i 个动物我开出三个点i表示“i 自己”这个角色i n表示“i 的猎物”这个角色i 2n表示“i 的天敌”这个角色。这样总节点数是 3n。初始时所有角色都各自成集合。接下来每来一条信息我不是只合并“两个元素”而是合并“相关的角色集合”。比如“X 和 Y 是同类”那意味着X 自己的集合和 Y 自己合并X 的猎物集合和 Y 的猎物合并X 的天敌集合和 Y 的天敌合并。也就是把三个角色完全对齐。“X 吃 Y”怎么合并这句话等价于X 的猎物是 YX 是 Y 的天敌同时 X 的天敌是 Y 的猎物因为食物链是一个环A吃B、B吃C、C吃A所以天敌的猎物之间也有关联。所以要做三次合并void unite(int x, int y) { int fx find(x), fy find(y); if (fx ! fy) fa[fx] fy; } void same(int x, int y) { // 声明x和y是同类 unite(x, y); unite(x n, y n); unite(x 2 * n, y 2 * n); } void eat(int x, int y) { // 声明x吃y unite(x n, y); // x的猎物是y unite(x, y 2 * n); // x是y的天敌 unite(x 2 * n, y n); // x的天敌是y的猎物 }判断矛盾时也很直观。如果某句话声称“X 和 Y 是同类”但现有的并查集里已经有了find(X n) find(Y)说明 X 的猎物是 Y也就是 X 吃 Y或者find(X 2 * n) find(Y)说明 X 的天敌是 Y也就是 Y 吃 X那这句话就是假的。如果某句话声称“X 吃 Y”但现有的并查集里已经能推出find(X) find(Y)同类或者find(X 2 * n) find(Y)说明 X 的天敌是 Y也就是 Y 吃 X那它也是假的。这个思路的优势是逻辑清晰不太需要推导复杂的数学公式懂并查集基本操作的人很快能上手。缺点是空间变大了如果有 k 种角色就要开 k*n 的数组。但一般 k 都很小比如 2、3所以完全能接受。3.3 开两倍数组的典型场景朋友与敌人不只是三倍数组很多“二分关系”题目只需要开两倍数组。比如最常见的“朋友与敌人”问题A 和 B 是敌人B 和 C 是敌人问 A 和 C 是不是朋友。这种题的处理方式是i表示 i 所在的“朋友阵营”i n表示 i 所在的“敌人阵营”。当 X 和 Y 是朋友时合并X与Y合并Xn与Yn当 X 和 Y 是敌人时合并X与Yn合并Xn与Y。很多初学者会好奇为什么敌人关系要交叉合并因为如果 X 和 Y 是敌人那么 X 的朋友就是 Y 的敌人X 的敌人就是 Y 的朋友。这个交叉合并把“敌人的敌人是朋友”这条隐式规则编码进了并查集。一旦后续发现find(X) find(Y)说明朋友阵营重合那就矛盾了。所以种类并查集的本质是用“多开几个集合”的方式把原本只能表达“正反”两类关系的问题扩展为能够表达“正、反、中立”、“猎物、天敌、同类”等多角色关系。当你遇到“对于任意两个元素它们之间可能有多种互斥关系”的题目时第一时间就该想到扩展域。4. 带权并查集从“连通”升级到“距离”4.1 边上的权值到底在表达什么如果扩展域的核心是“多开几个集合”那带权并查集的核心就是“给每条边加一个数值”。这个数值可以表示相对关系、相对距离、奇偶差异等完全取决于题目语义。举个最简单的例子现在有一排位置每个位置放一个数字。告诉你一系列条件比如“区间 [l, r] 内所有数字的和是奇数”或者“A 比 B 的权重大 3 个单位”。你不仅要判断这些条件是否矛盾还要在某些情况下计算两个点之间的差值。这时候普通并查集的fa[x]只有一个父节点信息远远不够用。带权并查集的做法是在fa[x]之上再维护一个d[x]表示节点 x 到父节点fa[x]的“距离”或“关系值”在模 M 的意义下取值。这里的 M 取决于关系种类数或者问题的模数。比如食物链问题中0 表示同类1 表示吃2 表示被吃M3奇偶性问题中0 表示偶数1 表示奇数M2。当你查询根节点并做路径压缩时d[x]要一路累加上去最终变成 x 到根节点的权值。这个过程需要格外小心因为递归本身容易把顺序搞乱。4.2 路径压缩时的权值更新写法先看最常用的递归写法int fa[N], d[N]; // d[x] 表示 x 到 fa[x] 的权值模 mod int find(int x) { if (fa[x] x) return x; int root find(fa[x]); // 先递归找到根 d[x] (d[x] d[fa[x]]) % mod; // 此时 fa[x] 已经被递归地压缩为根了 fa[x] root; return fa[x]; }为什么这里d[x] d[fa[x]]是对的因为递归调用find(fa[x])之后fa[x]这个位置已经被更新成了整个集合的根同时d[fa[x]]也更新成了原 fa[x] 到新根的权值。所以 x 到根的权值 原来的 d[x]x 到旧父亲 旧父亲到根的权值 d[fa[x]]。最后赋值fa[x] root完成路径压缩。更保险的写法是先保存旧父节点int find(int x) { if (fa[x] x) return x; int old fa[x]; int root find(old); d[x] (d[x] d[old]) % mod; fa[x] root; return root; }两种写法本质一样第二种对新手更友好不容易在递归过程中被“奇怪的顺序”绕晕。4.3 合并时的权值推导别硬背公式要会推合并操作是带权并查集最容易出错的地方。假设现在有一条信息“x 和 y 的关系值为 r”仍然在模 M 意义下具体 r 的含义由题目定义。x 所在集合的根是fxy 所在集合的根是fy。我要把fx挂到fy下面那么新的d[fx]应该等于多少这里不能靠默写得自己推一遍。先明确符号d[x]表示 x 到fx的权值d[y]表示 y 到fy的权值题目给出的条件是 x 到 y 的关系值为 r。合并后fa[fx] fy我们需要的是d[fx]也就是 fx 到 fy 的权值。从 fx 出发沿着d[fx] d[x]这条路径能走到 x从 x 再到 y 需要关系 r从 y 再到 fy 需要d[y]。合并后整条路径应该自洽也就是说d[fx] d[x] r d[y]在模 M 意义下移项得到d[fx] d[y] - d[x] - r但不同题目的 r 方向定义不同有的定义是“x 到 y 的关系”有的是“y 到 x 的关系”所以代码里可能出现d[fx] (d[y] - d[x] r) % mod这样的式子也可能出现减号。关键是别背公式每次做新题时先画一条路径自己推一遍方向。实现时为了防止负数通常会这样写void merge(int x, int y, int r) { int fx find(x), fy find(y); if (fx fy) return; fa[fx] fy; d[fx] ((d[y] - d[x] r) % mod mod) % mod; }注意这行后面先取模再加mod再取模确保结果落在[0, mod-1]区间。4.4 实战理解奇偶性问题如何用带权并查集这类题的经典问法给你一个 01 序列然后给出一串条件每个条件说“区间 [l, r] 内 1 的个数是奇数还是偶数”让你判断最早在第几条条件处出现矛盾。思路是维护前缀和数组pre[i]区间 [l, r] 内的奇偶性等于pre[r] xor pre[l-1]。我们不需要知道前缀和的具体数值只需要知道任意两个前缀和的奇偶关系是否自洽。于是把pre[l-1]和pre[r]当成两个节点用带权并查集维护它们的异或值也就是模 2 意义下的差值。如果条件说区间内是“偶数个 1”则pre[l-1]和pre[r]奇偶性相同关系值 r 0如果条件说区间内是“奇数个 1”则pre[l-1]和pre[r]奇偶性不同关系值 r 1。每次拿到新条件先查询fx find(l-1)和fy find(r)。如果已经在同一个集合里就检查当前已知的d[l-1]和d[r]计算出的奇偶关系是否和题目给的一致不一致就是矛盾。如果不在同一个集合就执行带权合并。这种问题如果不提前想到“前缀和奇偶性”这个转化哪怕你背熟了带权并查集代码也想不到要这么用。所以带权并查集真正难的往往不是代码而是把题目条件抽象成“两个点的权值差”这个建模过程。多看几道典型题慢慢就会建立条件反射。5. 常见问题、调试技巧与适用场景速查5.1 那些年我踩过的并查集坑先列几个新手极容易踩的坑每一条我都亲眼见过或者自己踩过。第一初始化漏了。fa[i] i没写全或者下标从 0 开始但循环只到了 n-1查询时直接访问到没初始化的垃圾值。这是最基础但也最高发的错误没有之一。第二递归 find 爆栈。路径压缩并不是银弹如果并查集合并时没按秩合并又连续做了很多次合并递归深度仍然可能很大。比赛里我见过有人因为递归爆栈导致 RE而不是 WA。大数据量时建议还是写循环版。第三合并时根选反了。比如merge(x, y)里写成fa[y] x虽然对于普通并查集查询连通性影响不大但在带权并查集里方向一旦反了所有d的推导全部颠倒最后出一堆莫名其妙的结果。第四模运算负数处理。带权并查集的d[fx]计算时d[y] - d[x] r可能是负数。如果直接对负数取模不同语言对负数的处理不一样很容易出问题。统一写成((val) % mod mod) % mod。第五路径压缩时d[x]更新顺序错。新手容易写成d[x] d[fa[x]]但此时fa[x]已经是经过递归压缩后的根如果没先用一个临时变量保存旧父节点最后算出来的权值会差很远。5.2 一个很容易复制的调试套路调试并查集问题最直接的方法写一个小的暴力版本然后随机数据对拍。具体做法是维护一份朴素的、不含路径压缩的并查集或者直接在每次操作后用 DFS 遍历整个集合看连通关系再和优化版的答案对比。对拍数据要覆盖随机合并、随机查询、随机矛盾条件。一旦发现两边答案不一致立刻把出错的那组输入打出来手动模拟。如果只是单纯调试带权并查集很多人会盯着代码看半天也看不出所以然。我更喜欢在每个关键操作后打印fa数组和d数组比对样例的每一步。写一个简单的debug()函数输出所有节点的父节点和权值观察在哪一步开始和预期不符问题通常就一目了然。另一种有效手段是拿一道题的两个版本互相验证扩展域版本和带权版本各写一遍对拍验证这样不仅验证了代码正确性还能加深理解。我就曾经用食物链这题把扩展域和带权写法都写了一遍从此对带权并查集的公式推导有了一种“肌肉记忆”。5.3 哪些场景用普通、种类还是带权整理一个速查表方便做题时快速定位该用哪一型。场景类型推荐方案说明连通性判断、Kruskal 判环、连通块计数普通并查集路径压缩 按秩合并朋友与敌人、奇偶阵营、二分关系判断种类并查集扩展域至少开 2 倍数组食物链、三角捕食、多角色关系种类并查集或带权并查集扩展域开 3 倍数组带权用模 3区间奇偶性、前缀和差值判断带权并查集模 2转化为前缀和节点相对排名、相对差值关系带权并查集模根据题目求和/差值推导区间和校验、并查集维护偏移量带权并查集模可灵活选择前缀和思想这张表只是一个大方向实际题目经常要混合使用。比如某些题用种类并查集描述角色但每个角色内部还带权值那就要组合。5.4 复杂度与学习路径建议普通并查集在同时使用路径压缩和按秩合并后单次操作均摊时间复杂度为 O(α(n))这里 α(n) 是反阿克曼函数增长速度比 log n 还要慢得多在实际数据范围内完全可以当成常数看待。种类并查集因为多开了 k 倍数组空间是 O(kn)时间仍然是 O(α(kn))。带权并查集只在每次 find 时多做几次加法和取模时间依然稳定在接近常数的水平。学习路径上我不建议一上来就盯着黑皮书里的各种证明看。正确的顺序应该是先把普通并查集背熟然后用“食物链”这题分别用扩展域和带权写法各做一遍再做两道“奇偶游戏”和“带权排名”的题最后回头看原理。你会发现底色其实都是同一个东西在“合并集合”之上表达“关系”关系的表达要么靠多开集合要么靠边权。6. 写在最后一点个人的体会写并查集这几年我最大的感受是它是一个“易学难精”的典型。入门只需要 10 分钟但真正在题目里用对、用活需要积累很多模型。比如看到区间条件就想到前缀和节点看到多种角色关系就想到扩展域或带权这种条件反射不是靠背模板能建立的必须靠实战喂出来。我自己刷题时有个习惯每遇到一种新的“关系判定类”模型就会研究它能不能用并查集建模。就算某道题正解是线段树或者平衡树我也会先想想并查集版本的思路哪怕最后不用这个思考过程也让我对并查集的边界有了更清晰的认知。话说回来面试和考试里并查集的出现频率非常高性价比确实拉满。如果你正被这东西绕得头大不妨先把最基础的手写版跑通再用食物链练手我觉得收获会来得很快。