刷POJ的并查集题单有一道题绕不开A Bugs Life。我第一次做它的时候用普通并查集硬怼了半天WA了快十发才反应过来——这题根本不是“把虫子分成几堆”那么简单它需要给并查集的每条边加上权值去表示集合内元素之间的“关系”。后来思路打通发现这道题其实是带权并查集也叫种类并查集最经典的入门载体把这道题吃透后面遇到食物链、奇偶性判断那些进阶题基本就是套同一个模板的问题。这篇博文不打算只贴代码。我会从题目建模、权值维护原理、合并推导、代码实现、常见坑点一路讲下来把我自己从“普通并查集思维”切换到“带权思维”过程中的思考痕迹也一并写出来。适合人群很明确已经会写基础并查集find、union、路径压缩但还没接触过带权并查集的朋友或者刷过这题但只记住了题解、没想通原理的选手。如果你两个条件都不满足建议先补一下并查集基础再来看。1. 题目到底在说什么从题面到模型转换1.1 题面解读与问题本质题目本身是个很“有味道”的设定有n只虫子科学家做了m次观察每次观察会给出两只虫子的编号x和y表示“x和y是不同性别”。现在要你判断这些观察结果是否自相矛盾。通俗点说是否存在一种性别分配方案能让所有观察结果同时成立。我第一次做的时候想得很简单既然是判断矛盾那不就相当于给虫子染色两种颜色代表两种性别观察说“x和y不同色”那就检查是否冲突。这个思路方向是对的但问题在于题目给的观察是“增量式”的——你事先不知道所有关系只能一条一条读入每读一条就判断当前是否已经矛盾。显然需要一个能够动态维护“关系是否自洽”的数据结构这就是并查集登场的原因。关键要理解一句话并查集本质上是维护传递关系。普通并查集维护的是“谁和谁在同一个集合”这是一种等价关系自反、对称、传递。但“x和y是异性”并不是等价关系它不满足传递性——x和y异性y和z异性推不出x和z异性反而是同性。所以你不能简单地把x和y并进同一个集合。那该怎么办答案是依然用并查集但集合里存的是“已经建立关联的所有虫子”然后用一个额外数组记录每个虫子和它父节点之间的性别关系。这样任何两只虫子只要在同一个集合里我们就能通过关系值的复合运算推导出它们应当是同性还是异性。当一条新观察给出的关系与推导结果冲突时矛盾就出现了。1.2 为什么普通并查集不够用先复现一下我用普通并查集尝试时的失败过程。当时我想的是开两个“对立集合”一个表示“和x同性”一个表示“和x异性”。每读到一条观察x、y就把“与x同性的人”和“与y异性的人”合并把“与x异性的人”和“与y同性的人”合并。这个思路在逻辑上其实很接近正确答案实现也需要两个并查集但代码写起来别扭且容易出错而且一旦要推广到三类、多类关系比如食物链里吃与被吃这种“开多个集合”的方法就直接爆炸了。普通并查集还有一个更本质的问题它只能告诉你“两个元素在不在同一个集合里”但它无法告诉你“两个在同一个集合里的元素彼此是什么关系”。在很多现实问题里“在同一个集合”只是第一步你真正关心的是集合内部元素之间的相对关系。比如本题里两只虫子都在同一个集合但它们究竟是同性别还是异性别这信息普通并查集完全不存。带权并查集就是为解决这个问题而生的。做法是给并查集的每条“父子边”附加一个权值记录子节点与父节点之间的相对关系。在本题里这个权值只有两种取值——0表示“与父节点同性”1表示“与父节点异性”。这样整个并查集就变成了一张“带权关系图”每个节点到根节点的路径上把所有边权按规则复合就能得到该节点与根节点之间的关系两个节点之间的关系就等于它们各自到根节点关系的复合。这个模型是理解所有带权并查集题目的总钥匙。2. 带权并查集的原理拆解2.1 权值的定义与存储带权并查集在代码层面只比普通并查集多一个数组结构并不复杂。普通并查集只维护parent数组parent[x]表示x的父节点带权并查集额外维护一个rel数组也有人叫rank或weight名字无所谓rel[x]表示x与parent[x]的关系。在本题里我约定rel[x] 0表示x与parent[x]性别相同rel[x] 1表示x与parent[x]性别不同这里有个很重要的直觉既然只有两种性别关系也只有两种那用0和1编码就是最自然的选择。为什么强调“二进制”因为后面你会发现关系复合的运算会落到异或XOR上而二进制的0/1配合异或操作可以非常优雅地表达“关系叠加”的逻辑。如果关系种类更多比如三类就要用模运算来复合那是食物链那道题的事情现在先不管。初始化时每个节点的父节点都是它自己rel[x] 0。自己和自己当然是同性关系所以是0这个细节不要想当然地写成别的值。想想看如果初始化时rel[x]被错误地设为1find函数一执行结果整个关系系统就乱套了。存储上还有一个常见的实现变体有些人用rank数组来表示“相对根节点的关系”而不是“相对父节点的关系”两者在代码细节上有差异但核心思想一致。我推荐“相对父节点”这种定义因为它在路径压缩和合并时的推导更直观也是大多数参考实现采用的约定。你只要选一种自己写起来顺手的一直用下去就行最忌讳的是混用两种定义代码写着写着就全乱了。2.2 路径压缩时如何维护权值普通并查集的find函数做路径压缩时只需要把沿途节点直接挂到根节点下面这大家都知道。但带权并查集多了一个问题路径压缩会改变节点的父节点那么rel[x]也必须跟着更新——原来rel[x]表示x与旧父节点的关系现在父节点变成了根节点rel[x]就应该表示x与根节点的关系。这里的关键规律是x与根节点的关系等于x与旧父节点的关系复合旧父节点与根节点的关系。在本题0/1异或的编码下这个“复合”就是异或运算。也就是说rel[x]新相对根 rel[x]旧相对父 XOR rel[旧父]相对根具体到代码递归版本的find函数是这么写的int find(int x) { if (parent[x] x) return x; int oldParent parent[x]; int root find(oldParent); rel[x] ^ rel[oldParent]; return parent[x] root; }注意看顺序先递归找根再更新rel[x]最后做路径压缩。其中oldParent这一行是必不可少的关键——因为递归调用结束后parent[x]已经被改成root了如果直接写rel[x] ^ rel[parent[x]]这里的parent[x]已经指向根节点而rel[parent[x]]其实是根节点到自己的关系永远是0这样就把原来的关系信息弄丢了。你可能会问为什么不是先更新rel[x]再递归因为rel[oldParent]这个值必须等递归跑完、路径压缩完成之后才已经更新为“oldParent到根的关系”。你必须在递归之前先把oldParent存下来递归之后再拿这个旧父节点去取已经被更新过的关系值。这个顺序感是写带权并查集最容易出错的地方我早期至少在这上面栽过五六次。用语言描述路径压缩后的效果经过find(x)之后parent[x]直接指向根rel[x]则记录了x到根的完整关系。这个关系是沿途所有边权复合的结果等价于把x到根的路径上每条边的性别关系依次“叠乘”起来。就像你沿着一条链路打听消息——“x和A性别不同A和B性别相同B和C性别不同”那么x和C就是性别相同因为“不同、相同、不同”这三个关系复合的结果是“相同”——这正是异或逐位运算的逻辑。3. 合并操作与矛盾判定的完整推导3.1 合并时权值的公式推导当读到一条观察“x和y是异性”时先分别找到x和y的根节点fx和fy。如果fx ! fy说明两个集合还没有建立关联需要合并。合并的关键问题是把fx挂到fy下面之后rel[fx]应该等于多少这一步是很多题解直接给结论、但不说推导过程的地方我详细推一遍。已知的信息有三条rel[x]x与fx的关系路径压缩后x已直连fx或者至少可以通过路径压缩得到rel[y]y与fy的关系题目说了x与y是异性也就是x与y之间的关系是1我们要推导的未知量是rel[fx]即fx与fy的关系假设把fx的父节点设为fy。把整条关系链写出来x —(rel[x])— fx —(rel[fx])— fy —(rel[y]反向)— y在0/1异或的世界里从x到y的复合关系 rel[x] XOR rel[fx] XOR rel[y]。注意这里rel[y]表示y到fy的关系而我们用的是fy到y的方向好在“性别关系”是对称的x与y性别不同等价于y与x性别不同反过来用rel[y]不会改变结果。这是本题关系的一大便利换成“谁吃谁”那种不对称关系这里就不能直接这样用了。那么题目要求x和y是异性即复合关系 1于是得到方程rel[x] XOR rel[fx] XOR rel[y] 1解这个方程两边同时异或上rel[x]和rel[y]异或操作满足交换律和结合律而且a XOR a 0a XOR 0 a得到rel[fx] rel[x] XOR rel[y] XOR 1这就是合并操作的核心公式。写代码就是一句话parent[fx] fy; rel[fx] rel[x] ^ rel[y] ^ 1;合并的方向本身没有硬性规定你可以把fx挂到fy下也可以把fy挂到fx下公式会相应变化——本质上是同一道方程的不同解法。我在写的时候习惯统一把fx挂到fy下面这样输出的测试信息打出来也更直观。带权并查集的合并不需要维护树的高度也就是不需要按秩合并因为路径压缩已经保证了均摊复杂度足够优秀加不加按秩影响不大。3.2 什么时机判定矛盾另一种情况如果fx fy说明x和y已经在同一个集合里它们之间的关系是已知的、可以计算出来的——就是rel[x] XOR rel[y]x与根的关系复合y与根的关系。如果这个计算结果等于1说明x和y确实是异性符合题目给的观察不矛盾如果等于0说明根据前面的观察x和y应当是同性但当前这条观察说它们是异性矛盾出现了。代码逻辑if (find(x) find(y)) { if ((rel[x] ^ rel[y]) ! 1) { conflict true; } } else { // 合并用上面推导出的公式 }注意这里有个小细节有些人在判断时写的是(rel[x] rel[y])想表达“同性则矛盾”。这个写法在只有两类关系时是对的因为rel[x] ^ rel[y] 0就是rel[x] rel[y]两者等价。但为了和关系复合的逻辑统一我建议还是写成异或判断后面学多类关系时不会转不过弯来。还有一个逻辑问题一旦发现矛盾是否还要继续读入数据从题意来看题目要求的是“是否存在矛盾”一旦矛盾出现答案已经确定了。但输入数据还要继续读完否则会影响后续测试用例的读取。我惯用的处理方式是设置一个flag如果已经矛盾了后续的观察语句照常读取但不做处理只把flag传到最后的输出判断里。千万不要在发现矛盾后直接break循环那样会导致后续输入错位整个程序输出全部乱套。4. 完整代码实现与细节注释4.1 核心函数实现先给出完整的find和unite实现这部分是所有带权并查集题目的通用骨架建议直接背下来再根据具体题目改关系复合的方式const int MAXN 2005; int parent[MAXN]; int rel[MAXN]; // 0表示与父节点同性1表示异性 void init(int n) { for (int i 1; i n; i) { parent[i] i; rel[i] 0; } } int find(int x) { if (parent[x] x) return x; int oldParent parent[x]; int root find(oldParent); rel[x] ^ rel[oldParent]; return parent[x] root; } void unite(int x, int y) { int fx find(x); int fy find(y); if (fx fy) return; parent[fx] fy; rel[fx] rel[x] ^ rel[y] ^ 1; }这里我觉得有必要强调一个细节unite里先调用了find(x)和find(y)这两个调用不仅仅是找根更重要的是它们把x和y都路径压缩并更新了rel[x]和rel[y]为相对根节点的值。正因为有了这两步合并公式里才能直接用rel[x]和rel[y]。如果find实现得不对、或者没有在合并前调用find那么rel数组里存的是相对父节点的关系拿来做复合就会得到错误结果。这个逻辑链条一定要想清楚。还有一个小优化如果已经在其他循环里判断过find(x)和find(y)相等了unite里其实可以再加一个“如果相等就直接return”的防空判断防止重复find导致不必要的开销。这属于锦上添花不影响正确性。4.2 主流程与输出格式主程序部分POJ这类题目的输入特点是第一行是测试用例组数T每组用例第一行是两个整数n和m接下来m行每行是一次观察。输出要求每组用例输出一行格式是“Scenario #i:”然后是“No suspicious bugs found!”或“Suspicious bugs found!”组与组之间要有一个空行。完整代码框架如下#include cstdio int main() { int T; scanf(%d, T); for (int cas 1; cas T; cas) { int n, m; scanf(%d%d, n, m); init(n); bool conflict false; for (int i 0; i m; i) { int x, y; scanf(%d%d, x, y); if (conflict) continue; int fx find(x); int fy find(y); if (fx fy) { if ((rel[x] ^ rel[y]) ! 1) { conflict true; } } else { parent[fx] fy; rel[fx] rel[x] ^ rel[y] ^ 1; } } printf(Scenario #%d:\n, cas); if (conflict) printf(Suspicious bugs found!\n); else printf(No suspicious bugs found!\n); if (cas ! T) printf(\n); } return 0; }关于输入输出坦率地说题目数据量不大用cin/cout也能过但我个人习惯在这种O(n)规模的数据上用scanf速度更稳而且处理多组测试用例时不容易出现因为cin不解除绑定导致的性能问题。输出要特别注意空行题目明确要求在每组Scenario之间输出一个空行但最后一组之后不要再额外输出空行否则一般会判定Presentation Error。这个细节WA了两次才记住。初始化和多组测试的配合也要注意每组的n不同数组大小只要大于所有用例的最大n就行但init(n)每轮必须调用把这次的n个节点的parent和rel全部重置。有人为了省事只重置要用到的部分如果上一组用例的n比这一组大残留的旧数据可能被误用这个bug非常隐蔽排查起来很痛苦。5. 常见错误与调试技巧5.1 我踩过的坑先说两个最经典的错误每个写过这题的选手几乎都犯过。第一个是find函数里更新顺序写错。有人图省事写成int find(int x) { if (parent[x] ! x) { rel[x] ^ rel[parent[x]]; parent[x] find(parent[x]); } return parent[x]; }第一眼看上去似乎没问题但仔细分析就会发现先更新rel[x]再递归find(parent[x])此时parent[x]还不是根rel[parent[x]]也还没有完成路径压缩后的更新你用的rel[parent[x]]是旧值不是“父节点到根的关系”。正确的复合关系必须是“x到旧父节点的关系”异或“旧父节点到根的关系”旧父节点到根的关系只有在递归完成之后才存在。所以必须先用oldParent保存旧父节点递归返回后再更新这是我反复强调的。第二个是误以为rel数组只在合并时需要更新而忽略路径压缩时也要更新。有些同学find写得正确但忘记在路径压缩后把rel[x]更新为“相对根”导致合并时算错。实际上只要find函数的rel更新写对了路径压缩后rel[x]自动就是相对根的关系这个不需要额外操心。关键在于find函数内部要写对。还有一类坑和输入相关读入时n和m的顺序。题目给的是一行两个整数n和m但有的同学惯性思维把第一个当作边数m把第二个当作点数n一上来就初始化错了。这种错误看输入输出样例就能发现但代价是浪费一次提交。我现在的习惯是先看题目描述里“第一行包含两个整数n和m”这种关键句而不是靠猜。5.2 如何快速定位问题如果你写完代码WA了我建议按以下顺序排查第一步确认find函数的结构。打印几组手动构造的小数据比如4只虫子、按特定顺序给观察手工模拟每个数组的更新过程这一步能过滤掉绝大部分逻辑错误。第二步在调试版代码里往find和unite的关键节点加输出printf(find(%d) - root %d, rel%d\n, x, fx, rel[x]);重点看每个节点路径压缩后的rel值是否和你手工推导的一致合并时算出的rel[fx]是否符合公式。第三步构造一个自洽用例和一个矛盾用例分别测试。自洽用例4只虫子观察为(1 2)、(3 4)、(1 3)这条链给出一组不矛盾的异性关系矛盾用例再加一条(2 4)按链推导2和4应当是同性如果程序判定No然后你又自洽地推导出矛盾那就是方向性错误。第四步检查输出格式。很多题目其实逻辑全对就是多了一个空行或少了一个空行提交上去反馈WA或PE。把输出样例原封不动地逐字节比对包括空格和换行这种问题一眼就能看出来。我个人的经验是带权并查集调试时不要只盯着代码看拿笔在草稿纸上画树结构把每条边的权值标出来然后模拟一次路径压缩和一次合并把数组的每个变化过程写下来。这个过程虽然慢但非常有助于把“抽象的关系复合”变成“具体的手算过程”一旦代码和手算结果对上了说明你对模型的掌握已经过关了。6. 从这道题延伸出去6.1 同类题目拓展A Bugs Life是带权并查集里最简单的“两类关系”题。把它吃透之后我强烈建议去刷一道经典题食物链。这道题把关系从两类扩展到三类——A吃B、B吃C、C吃A形成循环。你需要用模3加法代替异或来复合关系合并公式从rel[x] ^ rel[y] ^ 1变成更一般的带模运算表达式。虽然数值上复杂了一些但思维模型完全一样每个节点维护与父节点的相对关系路径压缩时复合关系合并时通过解方程求rel[fx]。另外一类常考变形是奇偶性问题比如给定区间内1的个数是奇数还是偶数判断给出的若干条件是否矛盾。这类题把“关系”抽象成前缀和的奇偶性本质还是两类关系异或运算直接适用。你会发现一旦理解“权值两个元素之间的相对状态”这个抽象不同类型的题目只是给同一个模板换了一套“关系编码”而已。刷这些题的一个共同方法论是不要背公式每次自己从头推导合并时的rel[fx]表达式。推导流程固定写出x到y的关系链列出已知关系设未知数rel[fx]解方程。熟练之后全程不超过30秒。6.2 带权并查集的通用模式总结一个可以套用到所有带权并查集的通用模式分三步第一步定义关系编码。想清楚题目有多少种状态、用什么数字编码。两类用0/1三类用0/1/2编码方式直接决定复合运算用异或还是模加。第二步定义复合运算。明确“相邻两条关系边复合”的规则。两类关系就是异或三类关系就是模加更高阶的情况根据题意设计。这一步是所有公式的来源。第三步写代码时严格遵循三条铁律find中先存旧父节点再递归后更新合并前必须调用find以刷新x和y的rel值合并时rel[fx]通过解关系链方程得到不要靠猜。我后来做带权并查集的题基本不再需要临时推导公式了——模式固定、代码骨架固定剩下的只是改改关系复合的表达式和判断矛盾的条件。这也是为什么我说A Bugs Life是最好的一块敲门砖因为它的编码最简单两种状态、复合运算最基础异或所有原理都可以很直观地讲清楚。食物链那些复杂场景本质上就是在这套骨架上多加了一个模3运算而已。这题我做过的版本至少写了四遍每一遍都比上一遍更清楚。现在回头看带权并查集难就难在一个认知转换把二维的“集合归属”升级为三维的“集合归属相对关系”。一旦这个模型在脑子里立起来你会发现刷算法题很多焦虑都消失了——因为你看得见的不是一道题而是一类题的共同骨架。