企业官网建设流程全解析

带权并查集和种类并查集，几乎是每个刷算法题的人绕不开的坎。POJ 1182食物链这道题，当年把我从“会套并查集模板”直接打回原形：普通模板只能告诉我两个元素是不是同一个集合，可这道题偏偏要维护“同类、吃、被吃”三种循环关系。题面给n个动物和k句话，让你按顺序统计哪些是假话，前前后后折磨了我不少时间。这篇文章就把这道题从题意、原理到代码的整个思考过程完整复盘一遍，无论你是准备复试机试还是打竞赛，耐心看完都应该能独立写出来。

1. 先看懂食物链的三种关系：普通并查集为什么失效

1.1 题意和假话判定规则

题面本身不复杂。有n个动物，编号1到n，它们被分成三类，三类之间遵循同一条环形食物链：A吃B，B吃C，C吃A。注意这不是“大鱼吃小鱼”的线性食物链，而是循环的，A吃B、B吃C、C吃A首尾相连。

接下来输入k句话，每句话有两种格式：一种是“x和y是同类”，另一种是“x吃y”。让你从头到尾按顺序处理，统计一共有几句是假话。

假话的判定规则可以归纳成三条：

1. 编号越界，也就是x或y大于n，直接算假话；
2. 当前这句话和之前已经确定为真的话产生矛盾，算假话；
3. 自己吃自己，也就是d=2且x=y，算假话。

第一条和第三条规则在输入时就能直接过滤掉，真正的核心难点在第二条：如何高效判断“之前的信息”和“当前这句话”是否冲突。

1.2 普通并查集只能回答“是不是同类”

看到“同类”两个字，第一反应往往是：这不就是并查集吗？把同类放一个集合，每次判断两个元素是否在同一集合里。

但仔细一想就发现事情没那么简单。普通并查集里每个元素只有一种身份，它只能告诉你“这两个人是不是同一个帮派的”。可是食物链里的动物同时存在三种关系，x吃y、y吃z、z吃x这三句话如果都成立，用普通并查集把x、y、z放进同一个集合，那个集合就只能表达“它们是一伙的”，完全无法区分到底是同类还是捕食关系。

也就是说，普通并查集的“边”没有方向，也没有权值，一旦要表达“谁吃谁”这种带方向的信息，就彻底失灵了。

于是就有了两条技术路线：一是给边加上权值，用0、1、2记录相对关系，这就是带权并查集；二是把每个动物拆成“自己、猎物、天敌”三个虚拟节点，把不同角色的关系摊开到并查集里，这就是种类并查集，也叫扩展域并查集。两条路都能AC，下面分别讲透。

2. 带权并查集的核心：用0/1/2记录节点与父亲的关系

2.1 关系值定义，以及为什么天然要模3

带权并查集，名字听起来高级，做法其实就是在原本的fa数组旁边再开一个rel数组。rel[x]记录的是“x和它的父节点fa[x]之间的关系”，我习惯采用一套经典定义：

• 0：x和fa[x]是同类；
• 1：x吃fa[x]；
• 2：x被fa[x]吃，也就是fa[x]吃x。

为什么是三个值而不是两个？因为题目中的关系一共三种，而且这三种关系构成一个循环群。你可以想象成石头剪刀布：布赢石头、石头赢剪刀、剪刀赢布，在这个环上每走三步就回到起点，模3取余正好对应这种循环。于是“关系传递”这条关键操作，就可以用“权值相加再取模”完成。

举个例子，如果x的父亲是p，p的父亲是root，已知x对p的关系是rel[x]，p对root的关系是rel[p]，那么x对root的关系就是：

(rel[x] + rel[p]) % 3

这个公式是整个带权并查集的基石，后面的路径压缩和合并公式全从它推出来。

2.2 路径压缩时，权值要跟着边一起更新

普通并查集路径压缩很简单，把x直接挂到根节点下面就行。带权并查集麻烦在，挂过去之后rel[x]必须同步更新，否则箭头关系就乱了。正确写法如下：

int find(int x) { if (fa[x] == x) return x; int p = fa[x]; // 先保存旧父节点 fa[x] = find(p); // 递归压缩，p 的 rel 已经更新 rel[x] = (rel[x] + rel[p]) % 3; return fa[x]; }

很多第一次写的人会把顺序搞反，先更新rel[x]再递归，结果p的rel还没压缩成“p对根的关系”，传给x的就是半成品。正确做法是先用临时变量p保存旧父节点，递归返回后，p已经直接挂在根下面，rel[p]也已经是p对根的关系，这时再执行rel[x] = (rel[x] + rel[p]) % 3才是完整的“x对根的关系”。

这一步想通了，带权并查集就算入门一半。真正的硬骨头在合并集合时的权值计算。

3. 合并时最绕的权值计算：一条公式推明白，别再背错符号

3.1 合并公式的完整推导过程

假设x的根是fx，y的根是fy，我们准备把fx挂到fy下面，并且设置rel[fx]。已知的信息有：题目要求x和y满足一个关系d，其中d=1表示同类，d=2表示x吃y；另外还有x到fx的关系rel[x]，y到fy的关系rel[y]。

合并之后，x到最终根fy的路径变成了x -> fx -> fy，所以x对fy的关系是：

(rel[x] + rel[fx]) % 3

而y对fy的关系就是rel[y]。现在要从“x和y的关系”反推rel[fx]。

这里需要引入一个“反向关系”的概念。如果rel[y]表示y对fy的关系，那么反过来，fy对y的关系就是(3 - rel[y]) % 3。因为三者循环，正向走一次和反向走一次加起来正好是3，取模就是0，相当于绕了一圈回到原点。

于是从x走到y可以拆成三段：先从x到fx，再从fx到fy，最后从fy反向走到y。整条路径的关系值就是：

x对y = (rel[x] + rel[fx] + (3 - rel[y])) % 3

题目要求这个值等于d - 1（d=1时值为0，代表同类；d=2时值为1，代表x吃y）。移项之后得到：

rel[fx] = (d - 1 + rel[y] - rel[x] + 3) % 3

这就是网上所有题解里那个“神神秘秘”的公式。注意末尾加3再整体模3，这是为了处理负数。C/C++里负数取模的结果还是负数，如果不做这步，d - 1 + rel[y] - rel[x]算出来可能是-2或者-1，直接放进数组就全乱了。

3.2 代入实际数值验证公式方向

光给公式不验证，很容易让人心里没底，我们找一个最简单的情况代入。

假设当前语句是x吃y，也就是d=2，并且x的根fx就是x自己，y的根fy就是y自己。此时rel[x]=0，rel[y]=0。代入公式：

rel[fx] = (1 + 0 - 0 + 3) % 3 = 1

按定义，1代表fx吃fy，也就是x吃y，和题目给出的关系完全一致。

再看同类的情况。假设d=1且两个节点都是各自的根，代入公式：

rel[fx] = (0 + 0 - 0 + 3) % 3 = 0

fx和fy变成同类，同样合理。

如果哪一天你要自己推导另一个方向的合并公式，核心思想就一句话：把一条路径拆成“正向边之和加反向边”，然后和题目要求的关系值对齐。很多选手抄错了公式，往往是rel[x]的定义方向不一样，比如有的题解把rel[x]定义成“父节点对x的关系”，那公式符号就全反了。所以我不太建议死记硬背公式，而是建议理解推导过程，遇到自定义的rel方向时现场推一遍，十分钟就能搞定。

4. 完整AC代码与判谎逻辑：注释级拆解

4.1 带权并查集的可运行代码

下面是一份完整可运行的C++代码。find负责路径压缩和权值更新，unite负责合并两个集合，主函数里做编号越界、自吃以及同根时的矛盾判断。

#include <cstdio> const int MAXN = 50005; int fa[MAXN], rel[MAXN]; // rel[x] 定义： // 0: x 与 fa[x] 同类 // 1: x 吃 fa[x] // 2: fa[x] 吃 x int find(int x) { if (fa[x] == x) return x; int p = fa[x]; fa[x] = find(p); rel[x] = (rel[x] + rel[p]) % 3; return fa[x]; } // 把 x 所在集合的根挂到 y 所在集合的根下面 void unite(int x, int y, int d) { int fx = find(x); int fy = find(y); fa[fx] = fy; rel[fx] = (d - 1 + rel[y] - rel[x] + 3) % 3; } int main() { int n, k; // 老题目输入格式流传版本多，用 while 循环读入更稳妥 while (scanf("%d%d", &n, &k) == 2) { for (int i = 1; i <= n; ++i) { fa[i] = i; rel[i] = 0; } int ans = 0; for (int i = 0; i < k; ++i) { int d, x, y; scanf("%d%d%d", &d, &x, &y); // 规则1：编号越界，直接假话 if (x > n || y > n) { ++ans; continue; } // 规则3：自己吃自己，直接假话 if (d == 2 && x == y) { ++ans; continue; } int fx = find(x); int fy = find(y); if (fx != fy) { // 目前没有矛盾，按真话合并 unite(x, y, d); } else { // 同一个集合内，用 rel 判断是否满足题述关系 if (d == 1) { if (rel[x] != rel[y]) ++ans; } else { if ((rel[x] - rel[y] + 3) % 3 != 1) ++ans; } } } printf("%d\n", ans); } return 0; }

4.2 主流程里容易忽略的处理细节

代码本身不长，但有几个细节值得单独拎出来说。

第一个是编号问题。题目的编号从1开始，代码里我直接用1到n作为下标，没有额外减1，这样数组大小开MAXN就够了。如果你习惯下标从0开始，那么读入后要做--x; --y;，否则边界判断会漏。

第二个是输入输出。k最大可以到100000级别，输入输出必须用scanf/printf。用cin即使关了同步，在部分评测环境里也很危险，这道题对IO效率有实打实的要求。写while (scanf("%d%d", &n, &k) == 2)包一层是经验之谈，因为这道题在各个老平台上的数据格式流传版本不一样，有的题面说多组数据，有的评测环境实际只跑一组。用while循环包住之后，单组只会执行一次，多组也能正确处理，算是零成本的防御性写法。

第三个是判断逻辑的顺序。规则1和规则3在进入并查集逻辑之前就要过滤掉。越界和自吃和之前的真话无关，属于绝对假话。如果这两条不先处理，后面可能会因为越界编号去访问数组越界，直接导致运行时错误。

第四个常见错法是“先合并再判断”。很多人写的时候图省事，先把x和y合并，再去看是否矛盾，结果真话假话混在一起，整个集合的关系被污染，后续所有判断全部失效。正确顺序永远是：先判断，不矛盾才合并，假话直接计数。

再补充一个非常隐蔽的坑：在fx != fy时，调用unite(x, y, d)之前，x和y已经分别执行过find，所以rel[x]和rel[y]此时已经是它们各自对根的关系，unite里的公式基于的正是这一点。如果你在unite内部又调用一次find，也不会出错，因为路径压缩是幂等的，但没必要。

4.3 关于递归栈的实测建议

调试的时候，有人可能会担心：每次都把fx挂到fy下面，不做按秩合并，极端情况下树会不会退化成长链，递归会不会爆栈？

实测n=50000这个量级，完全没问题。之所以敢这么写，是因为路径压缩的威力非常大，树高在大量查询后会迅速降低。就算某次构造出长链，评测递归栈也足够撑住。如果你实在不放心，可以加一个size数组做按秩合并，但注意rank变化时合并方向可能改变，rel[fx]公式也要跟着对称变化，容易写错。我的建议是新手期固定“把fx挂到fy下”这一个方向，别一边用按秩合并一边套固定公式，那才是真的会出bug。

5. 另一种思路：三倍空间的种类并查集怎么玩

5.1 把每个动物拆成“自己、猎物、天敌”三个位置

带权并查集的公式劝退了不少人，于是很多选手转而使用种类并查集，也叫扩展域并查集。思路非常直白：既然每个动物都有“自己、猎物、天敌”三种角色，那就把数组开成三倍，用三个不同区间的下标表示同一个动物的不同身份。

约定如下，动物编号1到n：

• x：动物x自己；
• x + n：被x吃掉的动物，也就是x的猎物集合；
• x + 2*n：吃掉x的动物，也就是x的天敌集合。

并查集里的“合并”现在有了新的含义：两个位置在同一个集合里，表示“这两个角色属于同一种动物”。比如把x + n和y合并，就表示“y属于x的猎物集合”，用自然语言说就是“x吃y”。

这种写法的好处是，所有关系都摊在fa数组里，调试时可以直接观察哪些角色被绑定在一起，不太容易绕晕。

5.2 同类与捕食关系的合并和矛盾判定

初始化时，把所有1到3*n的fa设为自己。接下来逐句处理。

当d=1，也就是x和y同类时，需要合并三组位置：

merge(x, y); // 同类 merge(x + n, y + n); // 它们的猎物相同 merge(x + 2*n, y + 2*n); // 它们的天敌相同

矛盾条件是：x已经在y的猎物集合里，或者y已经在x的猎物集合里。翻译成代码：

if (find(x) == find(y + n) || find(y) == find(x + n)) ok = false;

因为猎物关系和同类关系互斥，一旦出现了捕食绑定，就说明这句“同类”和之前的真话冲突。

当d=2，也就是x吃y时，处理稍微多一点。矛盾条件和合并操作如下：

if (find(x) == find(y) || find(x) == find(y + n)) ok = false; if (ok) { merge(x + n, y); // y 是 x 的猎物 merge(x, y + 2*n); // x 是 y 的天敌 merge(x + 2*n, y + n); // x 的天敌 和 y 的猎物 是同一种动物 }

前两条好理解，第三条很多人第一次看会懵：为什么x的天敌和y的猎物要合并？

因为这三类动物构成循环。设环是A吃B、B吃C、C吃A，x站在B的位置，y站在C的位置。那么x的天敌是A，y的猎物也是A，它们本来就是同一类动物。如果缺少这一条合并，某些传递链上的矛盾会漏判。具体来说，当你之后读到“A吃C”这类反向矛盾的句子时，可能因为A没有和C的猎物集合绑定而误判为真话。这是三倍并查集隐藏最深的一个坑。

5.3 三倍并查集和带权并查集怎么选

两种写法是对同一套关系模型的两种投影。带权并查集代码短、空间小、速度快，但公式晦涩，一旦抄反符号就全线崩溃；三倍并查集代码长一点，胜在逻辑直观，所有关系都能在fa数组里看得见摸得着。

我的建议是：如果你刚开始学，先用三倍并查集把这道题AC，把“同类合并三组、捕食合并三条”的规则吃透，然后回头再看带权并查集，会发现rel数组的公式不过是把三倍并查集的合并过程代数化、压缩到了一维。两种写法都理解了，这道经典题才算真正过关。

6. 从食物链出发：带权并查集的应用套路与我的实操心得

6.1 识别“循环关系”是解题第一道坎

食物链题的难点不在代码模板，而在于识别出“关系在模数意义下可传递”这一本质。很多问题表面上和动物无关，本质上却能套用带权并查集。

举几个常见方向：区间奇偶性问题，给出若干区间内1的个数是奇数还是偶数，让你判断是否矛盾，这时可以把前缀和的奇偶性当作权值，模2处理；某些“循环胜负”问题，A赢B、B赢C、C赢A，给出若干场比赛结果，问哪里有矛盾，这也就是把模3改成对应的比赛规则；再比如带方向的组队关系、带符号的等式系统，都可以抽象成“每个节点对父节点有一个关系值，关系值的传递满足某种代数运算”。

核心套路可以总结成四步：

1. 确定有哪些互斥的关系状态，构造一个循环群；
2. 给每个节点定义rel[x]，表明x和fa[x]的关系；
3. 推导路径压缩时的权值更新公式，通常就是两个rel相加取模；
4. 推导合并时新根的rel公式，通常就是路径拼接加反向关系。

只要把这四步走顺，任何带权并查集题目都能拆成“题意理解+公式推导+代码实现”三块，不再是无从下手的黑魔法。

6.2 我踩过的坑和几个固定习惯

写这道题的过程中，我至少踩过四五个坑，记下来给后来人避雷。

第一，所有减法先加模数再取模。我习惯把所有运算都写成(a + b) % MOD或者(a - b + MOD) % MOD，绝不直接对负数取模。C/C++的负数取模结果是负的，放进数组就是越界或者玄学错误，这类bug极难查。

第二，路径压缩里先存旧父节点再递归。这个前面说过，顺序错了关系权值就传错了。代码里int p = fa[x]; fa[x] = find(p); rel[x] = (rel[x] + rel[p]) % 3;这个三行顺序是神圣不可更改的。

第三，合并公式只背一个方向。我永远把fx挂到fy下面，所以rel[fx]的公式永远是(d - 1 + rel[y] - rel[x] + 3) % 3。一旦在某些代码里看到有人把fy挂到fx下面，公式变成(rel[x] - rel[y] - (d - 1) + 3) % 3，我会立刻警觉，分清方向再抄。

第四，初始化别漏了rel数组。有人只写fa[i] = i忘记初始化rel[i]=0，短数据碰巧能过，长链条下就会出问题。这个问题肉眼很难发现，建议直接写成for (int i = 1; i <= n; ++i) fa[i] = i, rel[i] = 0;一行搞定。

第五，多组输入的坑值得单独说一句。食物链题在国内各个老平台的评测数据格式不完全一致，有的题面写着多组，有的评测环境只跑单组。把读入写成while循环，单组时只执行一次，多组时也能正常跑完，这是一种零成本的稳妥写法。很多选手在这个地方白白WA好几次，纯粹是因为读入方式太死板。

6.3 两个版本都能AC，但你最好先理解再背模板

这篇文章写了两种解法，但我不建议你直接跳到代码复制粘贴。食物链题最大的价值，是逼你把“并查集只能合并同类”的思维升级成“并查集可以维护带方向的关系”。这个升级一旦完成，后面遇到扩展域并查集、带权并查集、甚至种类图上的判定问题，都会有种豁然开朗的感觉。

如果你正在准备机试，时间有限，至少要把带权并查集的rel数组定义、路径压缩写法、合并公式推导这三件事想明白。考试时即使紧张到记不住公式，也能在草稿纸上用“路径拼接+反向关系”现场推出来。这比背十遍答案都管用。