1. 并查集到底是啥一句话讲透核心用途如果你刷算法题或者准备面试大概率见过“并查集”这个名词很多教程上来就贴代码结果就是“看的时候懂合上就忘”。我试着用大白话把它讲清楚争取让零基础的小白也能直接上手。并查集英文叫 Disjoint Set Union缩写 DSU核心就干两件事把两个集合合并查两个元素在不在同一个集合里。听起来很抽象但你肯定遇到过类似场景——朋友圈里两个人是不是好友关系链上的游戏里两个玩家是不是同一个阵营力扣题“省份数量”“等式方程的可满足性”本质都是在判断“连接关系”。这类问题的共同点是一开始只有零散元素后来通过边、关系、条件在不断合并最后要快速回答“这两个东西现在是不是一家人”。为什么需要并查集因为如果你用最简单的方式存图、存邻接表每次查询连通性都要跑一遍遍历数据量一大就炸。并查集的妙处在于它用一棵棵“树”来组织关系每个集合选出一个“老大”查询时只问“你的老大是谁”合并时只改一个指针平均下来近乎常数时间。这就是它能在竞赛和面试中脱颖而出的原因。这篇我会从设计原理讲到完整代码再补充带权并查集这个高频进阶点最后附上我实际刷题遇到的坑和排查思路。无论你是刚学数据结构的新手还是想捡起这块内容准备面试都建议跟着代码亲手跑一遍。2. 拿帮派讲明白并查集的核心设计2.1 每个集合都有一个“老大”初识父节点数组并查集最核心的数据结构是一个一维数组一般叫parent或者fa。它的含义特别直白fa[i]表示元素 i 的“上级”是谁。我们不用管整棵树的形状只需要知道每个节点往上指到哪里。举个例子假设我们有 5 个人编号 0 到 4最开始谁都不认识谁那每个人都是自己的老大所以fa[i] i。初始化代码就是fa list(range(n))一行搞定。这个初始化很关键它意味着每个元素自成一个集合集合的代表元素就是自己。现在建立关系0 和 1 成为朋友我们让 1 的上级指向 0执行fa[1] 0。此时 1 所在集合的代表是 0接着 2 和 3 成为朋友让fa[3] 2。再往后2 和 0 成为朋友我们把 2 的上级指向 0注意此时 3 的上级还是 2但我们不需要改 3因为查询 3 时它会顺着 3 → 2 → 0 找到代表 0。这就是并查集的“懒”策略合并时只改一个指针所有细节留到查询时再处理。这个设计非常像现实中的帮派结构你只管认大哥大哥上面还有大哥迟早能摸到龙头。2.2 顺着线往上摸find 操作的秘密find(x)要做的事就是返回 x 所在集合的“老大”也就是根节点。实现方式是一个循环或递归不断往上走只要fa[x] ! x就继续x fa[x]最后返回 x。def find(x): while fa[x] ! x: x fa[x] return x这个朴素版本有三个问题。第一如果树退化成一条链比如每次都把新节点挂到根下面查询最后一个节点要一路走到头复杂度 O(n)。第二递归版本在链很长时可能爆栈。第三重复查询同一个节点时每次都走同样长的路非常浪费。解决的方案就是“路径压缩”。既然我这次已经顺着整条链走到了根干脆把路上经过的所有节点的父指针直接指向根下次再查就是一步到位。代码只需要加一行def find(x): if fa[x] ! x: fa[x] find(fa[x]) return fa[x]2.3 合并两个集合union 到底在干嘛合并操作也简单给定两个元素 a 和 b先分别找到它们的老大如果老大相同说明本来就在一个集合什么都不用做如果不同就让其中一个老大的父亲指向另一个老大。def union(a, b): ra, rb find(a), find(b) if ra ! rb: fa[ra] rb看到没有合并的其实是“根节点”。你可能想问让 ra 指向 rb 还是 rb 指向 ra有区别吗有而且影响不小。如果不加约束随便挂运气差的时候会形成一根长链查询效率就下来了。所以更稳妥的做法是“按秩合并”把层数更浅的树挂到更深的树上让整体高度增长尽可能慢。这里的“秩”可以简单理解成树的层数也可以用子树大小来衡量。size [1] * n def union(a, b): ra, rb find(a), find(b) if ra rb: return if size[ra] size[rb]: ra, rb rb, ra fa[rb] ra size[ra] size[rb]这个优化配合路径压缩并查集的单次操作复杂度可以视为阿克曼函数的反函数增长极其缓慢实操中基本就是常数时间。不过说实话纯刷题场景只写路径压缩也几乎不会超时按秩合并更像是一层保险帮你把最坏情况彻底干掉。3. 代码模板与关键优化细节3.1 一份能直接跑的 Python 模板我把平时做题最顺手的一套模板放出来你复制到本地改一改就能用。这套写法把find写成嵌套函数利用闭包直接操作fa省得每次传数组。class DSU: def __init__(self, n): self.fa list(range(n)) self.size [1] * n def find(self, x): if self.fa[x] x: return x self.fa[x] self.find(self.fa[x]) return self.fa[x] def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return if self.size[ra] self.size[rb]: ra, rb rb, ra self.fa[rb] ra self.size[ra] self.size[rb]用的时候n 5 dsu DSU(n) dsu.union(0, 1) dsu.union(2, 3) print(dsu.find(1) dsu.find(0)) # True print(dsu.find(0) dsu.find(2)) # False整个类的状态就是fa和size两个数组不需要维护别的结构省空间且逻辑清晰。每次操作后哪怕不打印你也能通过fa数组直观看到元素之间的挂接关系非常方便调试。3.2 路径压缩的实现差异路径压缩有两种写法区别在于递归栈的深度。递归版def find(x): if fa[x] ! x: fa[x] find(fa[x]) return fa[x]迭代版def find(x): root x while fa[root] ! root: root fa[root] while fa[x] ! x: nxt fa[x] fa[x] root x nxt return root递归版代码短好理解迭代版不会爆栈在节点数达到十万、百万级并且链很深时更稳。我个人做题一般写递归因为 Python 默认递归深度只有 1000 左右路径压缩后树的层数会非常浅基本不会踩坑但如果你拿 Java 或 C 写并且使用递归习惯记得留意栈空间限制。还有一个细节如果你在find里面顺手做了路径压缩那么union之后两个集合的树都会保持“相对扁平”的状态下次再查这两个节点效率极高。这也是为什么并查集即使不加按秩合并实战表现依然优秀的原因。3.3 关于按秩合并要不要每次都写初学者常问路径压缩都这么强了按秩合并是不是多余的我的习惯是“能写就写”。原因有两个。第一它可以把最坏情况下的树高控制在 O(log n) 级别即使路径压缩失效比如某些不支持递归的场景查询依然能接受。第二带权并查集的实现里有时需要依据秩来做合并方向的决策提前养成写size的习惯会顺手很多。但要注意union里交换根节点的写法不能乱来。比如上面模板中先比较size再让较小的根指向较大的根如果你把这步写成if size[ra] size[rb]: ra, rb rb, ra那后面fa[rb] ra指向的一定是大集合的根逻辑就对了。反过来如果你不交换而直接fa[ra] rb在某些题里虽然结果也对但树容易长歪后续查询性能会打折扣。提示路径压缩和按秩合并是两套独立优化可以分开使用。只做路径压缩时代码最短适合大部分笔试场景两者都做时理论性能最优适合追求极致稳定的场合。4. 带权并查集并查集的进阶钥匙4.1 什么是“权”为什么需要它基础并查集只回答“是否连通”但很多问题还要回答“连通之后两者的关系是什么”。比如在“食物链”问题中A 吃 BB 吃 CC 吃 A你需要知道任意两种动物之间的捕食关系在“银河英雄传说”中你需要知道两艘战舰之间隔了多少艘船在带权并查集里每条“父子关系”边上附加一个数值叫“权”表示子节点相对于父节点的偏移量。这个权值不是固定的它随查询动态更新。核心思路是每个节点到根节点之间存一个dis[x]表示 x 相对于根的距离或关系。合并时只要算清楚两个根之间的权值关系其余节点的值在路径压缩时顺便更新。做个生活化类比你在一个公司里每个人只知道自己的上级是谁同时知道自己和上级的职级差。通过一路向上加总你就能算出自己和 CEO 差几级。带权并查集干的就是这件事只不过它把“职级差”抽象成了任意的权值。4.2 关系偏移的经典模型食物链“食物链”是带权并查集最经典的应用没有之一。题目背景是三种动物 A、B、CA 吃 BB 吃 CC 吃 A。给你若干条“X 和 Y 是同类”或“X 吃 Y”的断言要你判断哪些断言和之前的已知信息矛盾。解法是用一个数组d[x]表示 x 与父节点之间的“关系”0 表示同类1 表示 x 被父节点吃2 表示 x 吃父节点。这里因为关系是循环的所以模 3 运算直接登场。find时先递归找到根然后d[x] (d[x] d[fa[x]]) % 3逻辑是把 x 到父节点的偏移和父节点到根的偏移拼起来。合并时稍微麻烦。如果两个元素已经在同一个集合里可以直接根据两者到根的偏移判断断言真假。如果不在同一个集合就需要把两棵树接起来计算新边的权值。假设要把 rx 所在的树接到 ry 所在的树上已知 d[x] 表示 x 与 rx 的关系d[y] 表示 y 与 ry 的关系那么 rx 相对于 ry 的关系就是(d[y] - d[x] relation) % 3这里的 relation 是断言给出的关系。代码里的顺序和符号要仔细核对否则很容易错。4.3 带权并查集的模板与取模陷阱分享一份我修改过多次的带权模板配合食物链类题目食用class WeightedDSU: def __init__(self, n): self.fa list(range(n)) self.dis [0] * n def find(self, x): if self.fa[x] x: return x root self.find(self.fa[x]) self.dis[x] self.dis[self.fa[x]] self.fa[x] root return root def union(self, x, y, relation): # relation 表示 x 与 y 的关系具体语义由题目定义 rx, ry self.find(x), self.find(y) if rx ry: return self.fa[rx] ry self.dis[rx] self.dis[y] - self.dis[x] relation最需要注意的是dis[rx]的赋值顺序必须放在fa[rx]修改之后、下次find(rx)之前。因为路径压缩时dis[x]的更新依赖dis[fa[x]]如果你先改了fa再算dis[rx]就相当于让 rx 直接挂到 ry 下面rx 到新根的权值正好是dis[rx]本身不需要再叠加别的值。实际操作中很多人习惯先算fa再算dis结果逻辑完全反了排查半天。取模操作的时机同样关键。所有涉及关系相加相减的地方都建议先取模再加一个 mod 防止负数。比如self.dis[rx] (self.dis[y] relation - self.dis[x]) % 3之后再在需要负数转为正数时手动 3。不要嫌麻烦这类题的 WA 大多出在负数取模上。注意带权并查集的“权值更新公式”不是背下来的而是要从“x 到 rx 的偏移、y 到 ry 的偏移、新关系”三段路径拼起来推导。每次做题前在草稿纸上画一条链把偏移量标好合并公式自然就出来了。5. 常见问题与排查技巧实录5.1 递归 find 导致栈溢出写递归版 find 时如果树的形状是一条长链递归层数可能非常大。Python 默认递归深度限制在 1000 层数据量稍大就直接 RecursionError。遇到这种情况第一反应不是把递归深度调大虽然sys.setrecursionlimit确实能救急而是检查find是否漏了路径压缩。如果你每次union都是把随机一个根挂到另一个根下面并且没有按秩合并那么链长可能接近 O(n)。但只要你写了递归路径压缩第一次查询最深的节点之后链就变平了后续递归深度大幅下降。因此爆栈通常意味着你在某个地方没有正确调用find或者把fa数组维护错了而不是递归本身有问题。迭代版 find 可以从根上消除爆栈隐患我在处理 10 万级以上节点时更倾向于迭代版兼顾稳健和速度。5.2 查询结果不对合并方向搞反一道题你写完了逻辑感觉没问题样例也过了提交上去却有几个点 WA。这类问题在并查集题里特别常见。排查时先输出每一步的fa数组和关键查询结果肉眼比对。我印象最深的一个案例是带权并查集的合并公式里dis[x]和dis[y]的时间点问题。find(x)和find(y)会分别路径压缩 x 和 y压缩完成后dis[x]和dis[y]已经是相对于各自根节点的值。如果你在合并前先调用了find那么后续直接用压缩后的值计算没问题如果你没有先find就用旧的dis参与计算结果就全乱了。这是新手最容易踩的坑之一。5.3 带权并查集取模负数导致的错判食物链这类题目关系用 0、1、2 表示运算过程随时可能出现负数。比如计算(d[y] - d[x] relation) % 3如果d[y] - d[x] relation是负数Python 的%结果是正余数这还好但 C 和 Java 里负数取模还是负数直接拿去比较就会出问题。所以无论什么语言统一写成((d[y] - d[x] relation) % 3 3) % 3保证结果落在 0 到 2 之间。另外一个容易忽略的点是题目里关系编号和你代码里的映射要完全一致。比如“x 吃 y”和“y 吃 x”在公式里体现为 relation 的正负如果题目给的编号是 1 代表吃代码里却按 0 代表吃那所有合并公式都会偏移调试起来极其头疼。建议做题前先把映射关系写在注释里例如# 0: 同类1: x吃y2: y吃x。5.4 并查集“只压缩不合并”导致孤立集合有一种情况是你完成了所有union但查询时发现两个应该在集合里的元素不连通。问题往往出在“合并时没先查根”。比如有人把union写成直接把fa[a] b而不是fa[find(a)] find(b)这样只把 a 的父指针改了a 所在集合里其他元素根本感知不到这次合并之后查询就漏了。务必在合并前先find取根。还有一种是初始化时fa数组没建全比如题目编号从 1 开始你初始化了list(range(n))但最大编号是 2n访问fa[x]直接越界。这种低级错误往往在自测小样例时看不出来数据一大就暴露。建议初始化时直接写成fa list(range(max_n 1))宁可多开一点。5.5 性能优化与调试建议实测下来并查集的性能瓶颈不在算法本身而在多余的find调用。有些题目会高频查询每次查询都顺手做路径压缩虽然平均很快但大量调用也有常数开销。如果卡常可以尝试把find改成非递归版本并减少union里的重复查找。调试并查集的一个好习惯是把fa数组的变化过程打印出来。你可以专门写一个 debug 函数def show(): print(fa) print(size)在每次union后调用配合小规模用例基本能一眼看出哪个节点的父指针挂错了。这个方法在带权并查集里尤其好用因为你还得看dis数组的变化。还有一个经验值如果你的算法题中并查集使用率很高比如 1 万个查询、每个查询做 3 次 find即使 O(n α(n))跑起来也只在毫秒级。所以除非题目数据量到百万级且卡常严苛否则不需要做太多微观优化把正确性保证好更重要。6. 最后分享一点实际做题的体会并查集是我刷题时使用频率最高的数据结构之一因为它代码短、思路直观而且适用范围极广。图论里判断连通性、最小生成树的 Kruskal 算法前置准备、离线查询的区间连通性都能靠它快速搞定。我自己有个习惯每学一个数据结构就找 5 道经典题反复刷直到不看模板也能流畅写出完整代码。并查集这组题我推荐这么练先做“省份数量”熟悉基础 union 和 find再做“等式方程的可满足性”体会并查集如何解决“矛盾判定”接着上“冗余连接”学会在合并时识别成环然后挑战“食物链”把带权并查集的取模运算吃透最后可以用“岛屿数量 II”这类题来检验自己对动态连通性的理解。另一个小技巧写并查集时一定要把find和union两个函数写到滚瓜烂熟最好形成肌肉记忆因为很多高阶题目并不会直接告诉你“这题用并查集”而是需要你在分析过程中自己判断。判断的标准很简单题目里有没有“合并集合”和“查询是否同一集合”这两种操作如果有十有八九就是并查集。踩过几次坑之后我现在每写完一个带权并查集模板都会专门构造一个小的循环验证用例把 0、1、2 三个元素两两合并检查最后dis数组是否满足关系传递。这一步能帮我快速确认公式里的符号有没有写反。你也可以照这个思路在正式提交前用最小用例验证方向。代码写得快很重要但写得对更重要尤其在时间紧张的比赛中多花一分钟验证往往能省下十分钟的调试。
并查集详解：从基础原理到带权并查集实战
1. 并查集到底是啥一句话讲透核心用途如果你刷算法题或者准备面试大概率见过“并查集”这个名词很多教程上来就贴代码结果就是“看的时候懂合上就忘”。我试着用大白话把它讲清楚争取让零基础的小白也能直接上手。并查集英文叫 Disjoint Set Union缩写 DSU核心就干两件事把两个集合合并查两个元素在不在同一个集合里。听起来很抽象但你肯定遇到过类似场景——朋友圈里两个人是不是好友关系链上的游戏里两个玩家是不是同一个阵营力扣题“省份数量”“等式方程的可满足性”本质都是在判断“连接关系”。这类问题的共同点是一开始只有零散元素后来通过边、关系、条件在不断合并最后要快速回答“这两个东西现在是不是一家人”。为什么需要并查集因为如果你用最简单的方式存图、存邻接表每次查询连通性都要跑一遍遍历数据量一大就炸。并查集的妙处在于它用一棵棵“树”来组织关系每个集合选出一个“老大”查询时只问“你的老大是谁”合并时只改一个指针平均下来近乎常数时间。这就是它能在竞赛和面试中脱颖而出的原因。这篇我会从设计原理讲到完整代码再补充带权并查集这个高频进阶点最后附上我实际刷题遇到的坑和排查思路。无论你是刚学数据结构的新手还是想捡起这块内容准备面试都建议跟着代码亲手跑一遍。2. 拿帮派讲明白并查集的核心设计2.1 每个集合都有一个“老大”初识父节点数组并查集最核心的数据结构是一个一维数组一般叫parent或者fa。它的含义特别直白fa[i]表示元素 i 的“上级”是谁。我们不用管整棵树的形状只需要知道每个节点往上指到哪里。举个例子假设我们有 5 个人编号 0 到 4最开始谁都不认识谁那每个人都是自己的老大所以fa[i] i。初始化代码就是fa list(range(n))一行搞定。这个初始化很关键它意味着每个元素自成一个集合集合的代表元素就是自己。现在建立关系0 和 1 成为朋友我们让 1 的上级指向 0执行fa[1] 0。此时 1 所在集合的代表是 0接着 2 和 3 成为朋友让fa[3] 2。再往后2 和 0 成为朋友我们把 2 的上级指向 0注意此时 3 的上级还是 2但我们不需要改 3因为查询 3 时它会顺着 3 → 2 → 0 找到代表 0。这就是并查集的“懒”策略合并时只改一个指针所有细节留到查询时再处理。这个设计非常像现实中的帮派结构你只管认大哥大哥上面还有大哥迟早能摸到龙头。2.2 顺着线往上摸find 操作的秘密find(x)要做的事就是返回 x 所在集合的“老大”也就是根节点。实现方式是一个循环或递归不断往上走只要fa[x] ! x就继续x fa[x]最后返回 x。def find(x): while fa[x] ! x: x fa[x] return x这个朴素版本有三个问题。第一如果树退化成一条链比如每次都把新节点挂到根下面查询最后一个节点要一路走到头复杂度 O(n)。第二递归版本在链很长时可能爆栈。第三重复查询同一个节点时每次都走同样长的路非常浪费。解决的方案就是“路径压缩”。既然我这次已经顺着整条链走到了根干脆把路上经过的所有节点的父指针直接指向根下次再查就是一步到位。代码只需要加一行def find(x): if fa[x] ! x: fa[x] find(fa[x]) return fa[x]2.3 合并两个集合union 到底在干嘛合并操作也简单给定两个元素 a 和 b先分别找到它们的老大如果老大相同说明本来就在一个集合什么都不用做如果不同就让其中一个老大的父亲指向另一个老大。def union(a, b): ra, rb find(a), find(b) if ra ! rb: fa[ra] rb看到没有合并的其实是“根节点”。你可能想问让 ra 指向 rb 还是 rb 指向 ra有区别吗有而且影响不小。如果不加约束随便挂运气差的时候会形成一根长链查询效率就下来了。所以更稳妥的做法是“按秩合并”把层数更浅的树挂到更深的树上让整体高度增长尽可能慢。这里的“秩”可以简单理解成树的层数也可以用子树大小来衡量。size [1] * n def union(a, b): ra, rb find(a), find(b) if ra rb: return if size[ra] size[rb]: ra, rb rb, ra fa[rb] ra size[ra] size[rb]这个优化配合路径压缩并查集的单次操作复杂度可以视为阿克曼函数的反函数增长极其缓慢实操中基本就是常数时间。不过说实话纯刷题场景只写路径压缩也几乎不会超时按秩合并更像是一层保险帮你把最坏情况彻底干掉。3. 代码模板与关键优化细节3.1 一份能直接跑的 Python 模板我把平时做题最顺手的一套模板放出来你复制到本地改一改就能用。这套写法把find写成嵌套函数利用闭包直接操作fa省得每次传数组。class DSU: def __init__(self, n): self.fa list(range(n)) self.size [1] * n def find(self, x): if self.fa[x] x: return x self.fa[x] self.find(self.fa[x]) return self.fa[x] def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return if self.size[ra] self.size[rb]: ra, rb rb, ra self.fa[rb] ra self.size[ra] self.size[rb]用的时候n 5 dsu DSU(n) dsu.union(0, 1) dsu.union(2, 3) print(dsu.find(1) dsu.find(0)) # True print(dsu.find(0) dsu.find(2)) # False整个类的状态就是fa和size两个数组不需要维护别的结构省空间且逻辑清晰。每次操作后哪怕不打印你也能通过fa数组直观看到元素之间的挂接关系非常方便调试。3.2 路径压缩的实现差异路径压缩有两种写法区别在于递归栈的深度。递归版def find(x): if fa[x] ! x: fa[x] find(fa[x]) return fa[x]迭代版def find(x): root x while fa[root] ! root: root fa[root] while fa[x] ! x: nxt fa[x] fa[x] root x nxt return root递归版代码短好理解迭代版不会爆栈在节点数达到十万、百万级并且链很深时更稳。我个人做题一般写递归因为 Python 默认递归深度只有 1000 左右路径压缩后树的层数会非常浅基本不会踩坑但如果你拿 Java 或 C 写并且使用递归习惯记得留意栈空间限制。还有一个细节如果你在find里面顺手做了路径压缩那么union之后两个集合的树都会保持“相对扁平”的状态下次再查这两个节点效率极高。这也是为什么并查集即使不加按秩合并实战表现依然优秀的原因。3.3 关于按秩合并要不要每次都写初学者常问路径压缩都这么强了按秩合并是不是多余的我的习惯是“能写就写”。原因有两个。第一它可以把最坏情况下的树高控制在 O(log n) 级别即使路径压缩失效比如某些不支持递归的场景查询依然能接受。第二带权并查集的实现里有时需要依据秩来做合并方向的决策提前养成写size的习惯会顺手很多。但要注意union里交换根节点的写法不能乱来。比如上面模板中先比较size再让较小的根指向较大的根如果你把这步写成if size[ra] size[rb]: ra, rb rb, ra那后面fa[rb] ra指向的一定是大集合的根逻辑就对了。反过来如果你不交换而直接fa[ra] rb在某些题里虽然结果也对但树容易长歪后续查询性能会打折扣。提示路径压缩和按秩合并是两套独立优化可以分开使用。只做路径压缩时代码最短适合大部分笔试场景两者都做时理论性能最优适合追求极致稳定的场合。4. 带权并查集并查集的进阶钥匙4.1 什么是“权”为什么需要它基础并查集只回答“是否连通”但很多问题还要回答“连通之后两者的关系是什么”。比如在“食物链”问题中A 吃 BB 吃 CC 吃 A你需要知道任意两种动物之间的捕食关系在“银河英雄传说”中你需要知道两艘战舰之间隔了多少艘船在带权并查集里每条“父子关系”边上附加一个数值叫“权”表示子节点相对于父节点的偏移量。这个权值不是固定的它随查询动态更新。核心思路是每个节点到根节点之间存一个dis[x]表示 x 相对于根的距离或关系。合并时只要算清楚两个根之间的权值关系其余节点的值在路径压缩时顺便更新。做个生活化类比你在一个公司里每个人只知道自己的上级是谁同时知道自己和上级的职级差。通过一路向上加总你就能算出自己和 CEO 差几级。带权并查集干的就是这件事只不过它把“职级差”抽象成了任意的权值。4.2 关系偏移的经典模型食物链“食物链”是带权并查集最经典的应用没有之一。题目背景是三种动物 A、B、CA 吃 BB 吃 CC 吃 A。给你若干条“X 和 Y 是同类”或“X 吃 Y”的断言要你判断哪些断言和之前的已知信息矛盾。解法是用一个数组d[x]表示 x 与父节点之间的“关系”0 表示同类1 表示 x 被父节点吃2 表示 x 吃父节点。这里因为关系是循环的所以模 3 运算直接登场。find时先递归找到根然后d[x] (d[x] d[fa[x]]) % 3逻辑是把 x 到父节点的偏移和父节点到根的偏移拼起来。合并时稍微麻烦。如果两个元素已经在同一个集合里可以直接根据两者到根的偏移判断断言真假。如果不在同一个集合就需要把两棵树接起来计算新边的权值。假设要把 rx 所在的树接到 ry 所在的树上已知 d[x] 表示 x 与 rx 的关系d[y] 表示 y 与 ry 的关系那么 rx 相对于 ry 的关系就是(d[y] - d[x] relation) % 3这里的 relation 是断言给出的关系。代码里的顺序和符号要仔细核对否则很容易错。4.3 带权并查集的模板与取模陷阱分享一份我修改过多次的带权模板配合食物链类题目食用class WeightedDSU: def __init__(self, n): self.fa list(range(n)) self.dis [0] * n def find(self, x): if self.fa[x] x: return x root self.find(self.fa[x]) self.dis[x] self.dis[self.fa[x]] self.fa[x] root return root def union(self, x, y, relation): # relation 表示 x 与 y 的关系具体语义由题目定义 rx, ry self.find(x), self.find(y) if rx ry: return self.fa[rx] ry self.dis[rx] self.dis[y] - self.dis[x] relation最需要注意的是dis[rx]的赋值顺序必须放在fa[rx]修改之后、下次find(rx)之前。因为路径压缩时dis[x]的更新依赖dis[fa[x]]如果你先改了fa再算dis[rx]就相当于让 rx 直接挂到 ry 下面rx 到新根的权值正好是dis[rx]本身不需要再叠加别的值。实际操作中很多人习惯先算fa再算dis结果逻辑完全反了排查半天。取模操作的时机同样关键。所有涉及关系相加相减的地方都建议先取模再加一个 mod 防止负数。比如self.dis[rx] (self.dis[y] relation - self.dis[x]) % 3之后再在需要负数转为正数时手动 3。不要嫌麻烦这类题的 WA 大多出在负数取模上。注意带权并查集的“权值更新公式”不是背下来的而是要从“x 到 rx 的偏移、y 到 ry 的偏移、新关系”三段路径拼起来推导。每次做题前在草稿纸上画一条链把偏移量标好合并公式自然就出来了。5. 常见问题与排查技巧实录5.1 递归 find 导致栈溢出写递归版 find 时如果树的形状是一条长链递归层数可能非常大。Python 默认递归深度限制在 1000 层数据量稍大就直接 RecursionError。遇到这种情况第一反应不是把递归深度调大虽然sys.setrecursionlimit确实能救急而是检查find是否漏了路径压缩。如果你每次union都是把随机一个根挂到另一个根下面并且没有按秩合并那么链长可能接近 O(n)。但只要你写了递归路径压缩第一次查询最深的节点之后链就变平了后续递归深度大幅下降。因此爆栈通常意味着你在某个地方没有正确调用find或者把fa数组维护错了而不是递归本身有问题。迭代版 find 可以从根上消除爆栈隐患我在处理 10 万级以上节点时更倾向于迭代版兼顾稳健和速度。5.2 查询结果不对合并方向搞反一道题你写完了逻辑感觉没问题样例也过了提交上去却有几个点 WA。这类问题在并查集题里特别常见。排查时先输出每一步的fa数组和关键查询结果肉眼比对。我印象最深的一个案例是带权并查集的合并公式里dis[x]和dis[y]的时间点问题。find(x)和find(y)会分别路径压缩 x 和 y压缩完成后dis[x]和dis[y]已经是相对于各自根节点的值。如果你在合并前先调用了find那么后续直接用压缩后的值计算没问题如果你没有先find就用旧的dis参与计算结果就全乱了。这是新手最容易踩的坑之一。5.3 带权并查集取模负数导致的错判食物链这类题目关系用 0、1、2 表示运算过程随时可能出现负数。比如计算(d[y] - d[x] relation) % 3如果d[y] - d[x] relation是负数Python 的%结果是正余数这还好但 C 和 Java 里负数取模还是负数直接拿去比较就会出问题。所以无论什么语言统一写成((d[y] - d[x] relation) % 3 3) % 3保证结果落在 0 到 2 之间。另外一个容易忽略的点是题目里关系编号和你代码里的映射要完全一致。比如“x 吃 y”和“y 吃 x”在公式里体现为 relation 的正负如果题目给的编号是 1 代表吃代码里却按 0 代表吃那所有合并公式都会偏移调试起来极其头疼。建议做题前先把映射关系写在注释里例如# 0: 同类1: x吃y2: y吃x。5.4 并查集“只压缩不合并”导致孤立集合有一种情况是你完成了所有union但查询时发现两个应该在集合里的元素不连通。问题往往出在“合并时没先查根”。比如有人把union写成直接把fa[a] b而不是fa[find(a)] find(b)这样只把 a 的父指针改了a 所在集合里其他元素根本感知不到这次合并之后查询就漏了。务必在合并前先find取根。还有一种是初始化时fa数组没建全比如题目编号从 1 开始你初始化了list(range(n))但最大编号是 2n访问fa[x]直接越界。这种低级错误往往在自测小样例时看不出来数据一大就暴露。建议初始化时直接写成fa list(range(max_n 1))宁可多开一点。5.5 性能优化与调试建议实测下来并查集的性能瓶颈不在算法本身而在多余的find调用。有些题目会高频查询每次查询都顺手做路径压缩虽然平均很快但大量调用也有常数开销。如果卡常可以尝试把find改成非递归版本并减少union里的重复查找。调试并查集的一个好习惯是把fa数组的变化过程打印出来。你可以专门写一个 debug 函数def show(): print(fa) print(size)在每次union后调用配合小规模用例基本能一眼看出哪个节点的父指针挂错了。这个方法在带权并查集里尤其好用因为你还得看dis数组的变化。还有一个经验值如果你的算法题中并查集使用率很高比如 1 万个查询、每个查询做 3 次 find即使 O(n α(n))跑起来也只在毫秒级。所以除非题目数据量到百万级且卡常严苛否则不需要做太多微观优化把正确性保证好更重要。6. 最后分享一点实际做题的体会并查集是我刷题时使用频率最高的数据结构之一因为它代码短、思路直观而且适用范围极广。图论里判断连通性、最小生成树的 Kruskal 算法前置准备、离线查询的区间连通性都能靠它快速搞定。我自己有个习惯每学一个数据结构就找 5 道经典题反复刷直到不看模板也能流畅写出完整代码。并查集这组题我推荐这么练先做“省份数量”熟悉基础 union 和 find再做“等式方程的可满足性”体会并查集如何解决“矛盾判定”接着上“冗余连接”学会在合并时识别成环然后挑战“食物链”把带权并查集的取模运算吃透最后可以用“岛屿数量 II”这类题来检验自己对动态连通性的理解。另一个小技巧写并查集时一定要把find和union两个函数写到滚瓜烂熟最好形成肌肉记忆因为很多高阶题目并不会直接告诉你“这题用并查集”而是需要你在分析过程中自己判断。判断的标准很简单题目里有没有“合并集合”和“查询是否同一集合”这两种操作如果有十有八九就是并查集。踩过几次坑之后我现在每写完一个带权并查集模板都会专门构造一个小的循环验证用例把 0、1、2 三个元素两两合并检查最后dis数组是否满足关系传递。这一步能帮我快速确认公式里的符号有没有写反。你也可以照这个思路在正式提交前用最小用例验证方向。代码写得快很重要但写得对更重要尤其在时间紧张的比赛中多花一分钟验证往往能省下十分钟的调试。
