提起并查集我的第一反应还是 POJ 1182 这道“食物链”。在这道题之前我理解的并查集就是“判断两个人是不是同一个帮派”合并集合、查祖先而已。直到被朋友按头刷了这道题我才发现并查集还有一个完全不同的维度在维护“连通性”的同时还能维护节点之间的相对关系。而这恰恰是带权并查集也叫种类并查集的核心价值。POJ 1182 食物链是一道极其经典的题目几乎每一个搞算法竞赛的人都在上面磨过。题目给你一群动物、三种物种、一条循环的食物链然后不断抛给你两句话“X 和 Y 同类”“X 吃 Y”要求你从前面的真话和假话里挑出假话的数量。难点不在于你懂不懂并查集而在于怎么把“同类”“吃”“被吃”这三种关系编码进并查集里让每条语句都可以被快速验证、快速合并。这篇文章我打算从题意讲起把带权并查集的前因后果彻底拆开为什么普通并查集不够用、模 3 编码是怎么回事、路径压缩和合并公式到底怎么推、代码怎么写不会 WA以及我调试过程中踩过的那些隐蔽的坑。适合还没做过这道题、或者做了但公式全靠背、想真正理解原理的朋友。看完你会觉得这种题其实一点都不玄它就是一个三维状态下的并查集运算。1. 题目背景一类普通并查集搞不定的关系问题1.1 题意重述与输入输出约定先说说题目本身。有 N 只动物编号从 1 到 N。动物分三类A、B、C它们之间满足一个环形食物链关系A 吃 BB 吃 CC 吃 A。也就是说这不是一条直线吃的链而是一个三角循环。接下来系统给你 K 条陈述每条陈述有两种格式1 X Y表示 X 和 Y 是同类。2 X Y表示 X 吃 Y。这些陈述里混着假话。假话的定义有三条X 或 Y 的编号大于 N属于非法输入直接算假话。当说话内容是“X 吃 X”时即自己吃自己这在环形关系下不可能成立算假话。当前陈述与前面那些确定为真的陈述矛盾算假话。我们的目标就是输出这个 K 条陈述里一共有多少条假话。输出约定没什么特别的一个整数就行。但别小看这个题它之所以能成为带权并查集的经典入门题是因为你没法用一个普通的并查集去模拟这个“吃”的关系。1.2 为什么普通并查集在这里失灵普通并查集的本质是什么是维护“连通分量”。它只回答一个问题两个节点在不在同一个集合里。所以它擅长处理的是“这两个人是不是一个帮派的”“这两个城市的铁路通不通”这类二元关系。但食物链这道题要维护的是三类关系同类、吃、被吃。即使你知道 X 和 Y 在同一个集合里你还是不知道 X 到底是吃 Y、还是被 Y 吃、还是跟 Y 同类。这个信息在一次普通的 merge 之后就丢了。有人会说那我干脆把每种关系都单独拉一个并查集比如“吃”的集合一个、“被吃”的集合一个。听起来可行但你会发现“吃”和“被吃”是相对的X 吃 Y 就意味着 Y 被 X 吃这种关联关系很难用多个独立的集合表达干净。你需要的是一种能存“方向”的并查集。于是就有了带权并查集。它的思路特别朴素并查集不是一棵树吗那我就给每条树上边加一个权值这个权值表示子节点相对父节点的关系。这样我不仅知道两个节点连通还能沿着路径把它们的关系算出来。1.3 两类主流解法带权并查集与 3 倍空间拆点对付食物链这类“多态关系”题目业界有两套流传很广的解法带权并查集也叫种类并查集。用一个额外的数组 rel[x] 记录 x 与其父节点或者说最终与其根节点的关系。因为关系种类是 3 种所以用模 3 运算来传递。这也是本文的主角。3 倍空间拆点法。把每个动物拆成三个“虚拟节点”分别代表它属于 A 类、B 类、C 类。通过合并这些虚拟节点来表达约束用“是否有非法同集合出现”来判断真假。两种方法都能 AC时间复杂度也都是 O(K log N) 级别的但思维模式差别不小。带权并查集更考验公式推导拆点法更考验为每一个约束找到正确的并查集映射。我自己比较推荐先吃透带权并查集因为公式背后那套关系代数思想后面刷“关押罪犯”“相对关系判定”这类题都能用上。2. 带权并查集原理为什么模 3 够用关系怎么编码2.1 三类关系的模 3 编码要把关系放进并查集第一步是给关系编号。我用一个统一的规则0两个节点同类。1左边的节点吃右边的节点。2左边的节点被右边的节点吃。也就是说如果 R(u, v) 1表示 u 吃 vR(u, v) 2表示 v 吃 u或者说 u 被 v 吃。这 0、1、2 三个数字不是随便定的。仔细观察 A 吃 B、B 吃 C、C 吃 A 这个循环关系从“吃”到“被吃”再到“同类”本质上就是一个长度为 3 的循环。对一个长度为 3 的循环做加减运算最自然的方式就是模 3。你可能会想为什么食物链是循环的不是条状的因为题目明确给了 A 吃 B、B 吃 C、C 吃 A这本身就是模 3 的循环结构。用生活里的类比来说这就像轮班表。周一到周日是循环的如果只知道今天是周三、过了两天是周五那你用的是加法加上取模。食物链的关系传递也是一样两个节点的相对关系可以通过中间节点一步步算出来每一步就对应一次加法最后取模 3得到的一定还是 0、1、2 中的一个。2.2 并查集树上的带权边rel 数组的两种视角接下来考虑在并查集这棵树上怎么存关系。每个节点 x 有一个父节点 fa[x]我额外开一个数组 rel[x]用来表示 x 与 fa[x] 的关系还是按照上面那套 0、1、2 编码。这里有一个容易绕晕的点也是全网很多博客写法不统一的原因rel[x] 到底表示“x 相对父亲”还是“x 相对根”取决于你什么时候看它。在路径压缩之前rel[x] 存的是 x 与它当前直接父亲的关系。在路径压缩之后因为 x 的父亲变成了根 rootrel[x] 就会被更新成 x 与根的关系。两种视角本质是同一套机制路径压缩的过程就是把从 x 到根这条路径上所有边的权值累加起来模 3最后得到 x 与根的关系。所以最终每个节点都变成直接挂在根上同时记录自己相对于根的关系。这个设计解掉了 1.2 里的难题如果两个节点 x、y 在同一个集合里它们都直接和根相连那么 x 和 y 的相对关系可以这样算R(x, y) (rel[x] - rel[y] 3) % 3为什么是减因为 R(x, y) 可以拆成 R(x, root) R(root, y)而 R(root, y) 就是 -R(y, root)也就是 -rel[y]。整个过程等效于向量相减所以在模 3 下是 (rel[x] - rel[y]) 再补个 3 防负。2.3 关系传递的代数直觉R(a,c) R(a,b) R(b,c) (mod 3)我知道直接扔公式大家容易懵这里多说一句关系代数。假设有三个人a、b、c我知道 a 对 b 的关系、b 对 c 的关系那么 a 对 c 的关系就是两者相加再取模。举个例子和食物链对应如果 a 吃 b记 R(a,b) 1b 吃 c记 R(b,c) 1。那么 a 对 c 是什么关系按照食物链循环a 吃 b、b 吃 c、c 吃 a所以当 a 是 A、b 是 B、c 是 C 时a 和 c 的关系是 c 吃 a也就是 R(a,c) 2。而 1 1 2完美对应。这就是带权并查集的地基树上任意一条路径的边权可以累加。并查集的作用就是把这棵树的路径压缩掉让我们能用 O(1) 时间查询两个节点的相对关系。3. 核心实现find 路径压缩与 union 偏移怎么写才对3.1 find 的正确写法先保存旧父亲再更新 rel先说路径压缩。上节说的“把路径上的边权累加”落实到代码就是 find 函数里那三行int find(int x) { if (fa[x] x) return x; int old fa[x]; fa[x] find(fa[x]); rel[x] (rel[x] rel[old]) % 3; return fa[x]; }这里有个很重要的细节必须先保存旧父亲。当你调用 find(fa[x]) 之后fa[x] 已经被更新成根节点了如果你在递归返回后再去读 rel[fa[x]]读到的就是根节点的 rel通常是 0会导致整个关系链断裂。为什么 old 的 rel 在递归后是 old 与根的关系因为 find(old) 会递归压缩 old 那条链让 old 也直接挂到根上rel[old] 随之更新。所以 rel[x] 原x与oldfather关系 oldfather与root关系正好等于 x 与 root 的关系。每次 find 之后x 的父亲就是根rel[x] 就是 x 相对根的关系。我的代码里 fa 数组和 rel 数组都从 1 开始用下标 0 留着不用。3.2 union 的公式推导从路径恒等式出发接下来是重头戏合并两个集合时rel 值该怎么定。假设 x 所在集合的根是 fxy 所在集合的根是 fy现在有一条真实话x 与 y 的关系是 d-1规定 d1 时同类所以关系是 0d2 时 x吃y关系是 1。我决定把 fx 挂到 fy 下面也就是执行 fa[fx] fy。那么问题来了fx 相对新的父节点 fy 的关系 rel[fx] 应该填多少这个值不能乱猜从关系恒等式可以算出来。已知rel[x] 是 x 相对 fx 的关系即 R(x, fx)。rel[y] 是 y 相对 fy 的关系即 R(y, fy)。结合路径的可加性x 到 y 的关系可以拆成R(x, y) R(x, fx) R(fx, fy) R(fy, y)。注意最后一项 R(fy, y) 等于 -R(y, fy)也就是 -rel[y]R(fx, fy) 正是我们要填的 rel[fx]。而 R(x, y) 根据当前这条真话是 d-1。于是d - 1 rel[x] rel[fx] - rel[y]移项得到rel[fx] (rel[y] - rel[x] d - 1) % 3代码里为了防负写成rel[fx] (rel[y] - rel[x] d - 1 3) % 3;这是整个算法最核心的公式。很多人背不下来是因为没有从最原始的关系恒等式去理解。你只需要记住x 到 root 的关系 要填的 rel[fx] —— 中间经过 fx —— 然后回到 y 的关系差一切都能推出来。3.3 判断语句真伪先看是否在同一集合处理每一条陈述的时候我先把非法情况过滤掉x 或 y 越界直接 anscontinue。如果 d2 且 xy自己吃自己同样 anscontinue。然后做 find 查询如果 fx ! fy说明 x 和 y 之前没有任何约束关系那么这条陈述不可能和任何已知真话矛盾所以它一定为真。于是执行合并操作把两个连通分量连接起来。如果 fx fy说明 x 和 y 已经在同一个集合里它们的关系已经被之前的话约束住了。我们直接算 R(x,y) (rel[x] - rel[y] 3) % 3看它等不等于 d-1。相等就是真话不等就是假话。这里有个新手经常困惑的点为什么不在同一集合就一定是真话因为并查集里每个集合代表一组相互之间关系已经确定的动物不同集合之间没有任何已确定的关系。当前话给了它们一个关系我们可以自由地把两个集合拼起来不存在矛盾。这个“自由拼装”是并查集解题的一个核心思维。3.4 完整可交的 C 代码说再多不如贴代码下面是我调通过的一份完整实现#include cstdio const int MAXN 50010; int fa[MAXN], rel[MAXN]; // rel[x] 表示 x 与 fa[x] 的关系0同类1 x吃fa[x]2 x被fa[x]吃 int find(int x) { if (fa[x] x) return x; int old fa[x]; fa[x] find(fa[x]); rel[x] (rel[x] rel[old]) % 3; return fa[x]; } int main() { int n, k; scanf(%d%d, n, k); for (int i 1; i n; i) { fa[i] i; rel[i] 0; } int ans 0; while (k--) { int d, x, y; scanf(%d%d%d, d, x, y); if (x n || y n || (d 2 x y)) { ans; continue; } int fx find(x); int fy find(y); if (fx ! fy) { fa[fx] fy; rel[fx] (rel[y] - rel[x] d - 1 3) % 3; } else { if ((rel[x] - rel[y] 3) % 3 ! d - 1) { ans; } } } printf(%d\n, ans); return 0; }这份代码我建议你别直接抄完拉倒自己照着推一遍 find 和合并公式。真的理解了后面遇到带权并查集的变形题才能举一反三。4. 假话判定与合并细节里的坑4.1 三类假话的处理顺序千万别颠倒题目给了三类假话处理顺序有讲究先判越界和“X吃X”再判逻辑冲突。为什么不先判逻辑冲突因为如果 x 或 y 大于 n我们的 fa 数组、rel 数组可能根本没有对应位置直接 find 大概率会越界或者返回错误结果。这类非法语句应该在一开始就拦下来。至于 d2 xy其实也可以交给后面的逻辑冲突去判因为 R(x,x) 一定等于 0而 d-1 等于 1必然冲突。但题目明确把它们列为假话而且提前判断可以少一次 find 递归顺手写掉就好。4.2 合并时 rel[fx] 公式的符号不能硬背我第一次做的时候就是吃了“硬背公式”的亏。网上很多博客给出的合并代码有两种写法一种是 fa[fx] fyrel[fx] (rel[y] - rel[x] d - 1 3) % 3。另一种是 fa[fy] fxrel[fy] (rel[x] - rel[y] - (d - 1) 3) % 3。如果没看清别人把哪个根挂到哪个根下面直接抄公式WA 到怀疑人生。我自己后来养成了一个习惯每次写 union 之前先在草稿纸上写那个关系恒等式把 R(fx,fy) 独立出来再写代码。大致过程就是列路径x 到 fxfx 到 fyfy 到 y合起来等于 x 到 y。把已知项代进去。解出未知项 rel[fx]。只要每次都这么做符号就永远不会错。这个小习惯救了我后面好多带权并查集的题。4.3 rel 数组语义别在两种流派之间反复横跳读不同资料时你会发现rel 的编码有另一种写法0 同类1 表示 x 被父亲吃2 表示 x 吃父亲。方向是反的。两种流派都能 AC只是公式里的加法变成减法、正负号要跟着翻转。这个问题最坑的地方是你看着 A 博客的公式去套 B 博客的语义一旦对不上就开始怀疑自己哪里写错了越改越乱。我的建议是认准一套语义比如本文这套“0 同类、1 我吃父、2 父吃我”所有推导都在这套语义下完成。只要最终关系和判断公式自洽一定是对的。4.4 父节点数组与 rel 数组的初始化范围动物编号从 1 开始初始化 fa 和 rel 时循环写 for (i1; in; i)。有些人图省事写成 for (i0; in; i)数组开头是 0但业务数据从 1 开始等于漏掉了第 1 只动物而第 1 只动物的 fa 会是初始的 0导致后续 find 递归混乱。如果你习惯从 0 初始化那要保证业务数据也从 0 开始但 POJ 这题的输入明确从 1 开始所以循环必须对应上。rel 数组清零是必须的否则残留值会污染关系计算。5. 调试实录我在这道题上踩过的坑5.1 隐蔽 Bugfind 里不保存旧父亲这个 bug 我必须要单独拎出来说因为它完全不过本地样例一交上去就 WA。错误写法长这样int find(int x) { if (fa[x] x) return x; fa[x] find(fa[x]); rel[x] (rel[x] rel[fa[x]]) % 3; return fa[x]; }看起来好像没毛病递归返回后 fa[x] 已经是根了rel[fa[x]] 应该就是 rel[根]通常是 0那岂不是 rel[x] 不变对问题就在这里。我们想要的是 x 与“旧父亲”的关系加上旧父亲与根的关系但第二次访问 rel[fa[x]] 时旧父亲已经被更新成了根丢失了中间那一段信息。正确写法一定是在递归前把旧父亲先存下来参考 3.1 的代码。5.2 方向反了合并公式导致样例都过不了有时候样例都能过但提交就是 WA那多半是合并方向问题。我遇过一种情况手滑把 fa[fx] fy 写成了 fa[fy] fx但 rel[fx] 公式没变导致整个关系链符号颠倒。这种错误光看代码很难发现因为算法流程没毛病只是数学上不自洽。排查技巧自己构造一个小数据手动算。比如 n2第一句话“2 1 2”也就是 1 吃 2。如果代码输出 1判为假话那就是合并方向错了。手动推一遍合并前后 rel 的变化很快就能定位。5.3 输入效率cin 没关同步导致 TLEPOJ 这类老题库的数据量虽然不算夸张但 K 最多能到 100000如果直接 cin某些编译器版本下确实可能飘到超时边缘。我当时用的是scanf后来教别人刷题时有人用cin加ios::sync_with_stdio(false); cin.tie(nullptr);也能过。如果你从 Cin 开始就 TLE第一反应先检查输入输出效率别急着怀疑算法复杂度。5.4 常见问题速查表下面这份表是我从自己和朋友身上总结出来的遇到类似症状可以直接对号入座。错误现象可能原因排查与修复样例过提交 WA合并公式方向与 root 挂载方向不一致用关系恒等式重新推导 rel[fx]随机数据大量 WArel[x] 和 rel[fa[x]] 中一个是相对根、一个是相对父语义混用统一 rel 语义保证路径压缩后全变成相对根递归访问越界没判断 x n 就开始 find先把非法话拦掉答案全部偏大d 直接拿来当关系值没做 d-1检查 d-1 这件事是否在判断和合并时都用了TLEcin 未关同步 或用了复杂度更高的写法换 scanf或在多个查询场景下考虑非递归 find6. 拓展3 倍空间拆点法和带权并查集的对比6.1 3 倍空间拆点法的核心思路除了带权并查集食物链还有一种非常主流的写法就是 3 倍空间拆点法。原理是这样的把每个动物 x 拆成 3 个点分别表示“x 是 A 类”“x 是 B 类”“x 是 C 类”那么 i、in、i2n 这三者中最多只能有一个为真。当系统说 X 和 Y 是同类时我们就把 X 是 A 和 Y 是 A、X 是 B 和 Y 是 B、X 是 C 和 Y 是 C 分别合并。当系统说 X 吃 Y 时我们根据食物链循环把 X 的上一类跟 Y 的下一类对应合并比如 X 是 A 时 Y 必然是 BX 是 B 时 Y 必然是 CX 是 C 时 Y 必然是 A。判断假话也很直接如果“X 是 A”的虚拟节点和“Y 是 B”的虚拟节点已经连通而你又说 X 吃 Y那就矛盾了。这种方法胜在逻辑直观不需要做路径上的关系累加适合在考场上快速写出不容易错的代码。缺点是空间数组要开 3 倍判断条件里的索引映射比较繁琐。6.2 两种方案怎么选我自己做题的经历是刷题初期更喜欢拆点法因为每一句话对应的合并关系可以预先画出来照着抄不容易出错但拆点法在处理一些更复杂的相对关系问题时索引容易写乱而且空间常数较大。后期我转向带权并查集因为你一旦把关系代数搞顺了代码量反而更少公式更统一还能泛化到模 K 的问题上。这里给个对比方便你自己选择对比维度带权并查集3 倍空间拆点法空间复杂度O(N)O(3N)核心难点合并公式推导、方向符号虚拟节点索引映射代码量更短稍长泛化能力可推广到模 K 关系思路直观但推广时索引更复杂适合场景理解并查集本质后更推荐初学、面试快速写对6.3 带权并查集不止是模 3向模 K 推广带权并查集最漂亮的地方在于它那条“边权可加 路径压缩”的机制并不只适用于三态问题。你把模 3 换成模 K就可以表示 K 种两两之间的关系循环。比如某些题里关系是“顺时针相邻”“逆时针相邻”“同向”等多种状态只要这个状态能构成一个环状的群带权并查集就能处理。以后再遇到类似“有多种相对关系、且关系可传递”的题目不妨先想一想能不能把关系映射到 0 到 K-1 的数字上能不能定义一条运算规则让两个节点之间的关系通过中间节点累加得到如果可以那大概率就是一道带权并查集的应用题。回到这道食物链本身我最深的体会是算法竞赛里真正难的从来不是背结论而是把结论背后的代数结构搞清楚。当时我在合并公式上反复 WA后来静下心来把每个节点到根的关系当成向量来算所有公式一次写对。从那儿以后我遇到带权并查集的题都会先画关系链再写代码不再依赖“背公式”。如果你也在这道题上卡了很久不妨试试我这个方法把 R(a,c) R(a,b) R(b,c) 这条恒等式写在代码注释里推导的过程会比结果更有价值。