有段时间我在刷各大OJ的并查集专题POJ 2492 A Bugs Life 是印象很深的一道题。题面像一份生物实验报告第一遍读完全不知道要干什么等看懂之后才发现它要你判断的是一堆“异性关系”是否自相矛盾而解决它只需要一个带权并查集。这篇博文就围绕这道题展开把它拆成五个部分先还原题意再解释普通并查集为什么力不从心接着推导带权并查集的两个公式然后给完整可提交的AC代码并复盘我踩过的坑最后扩展一下同类型的题目。适合刚学完基础并查集想进阶的新手也适合面试前想快速回忆关系并查集的选手。1. 题意还原一场关于虫子恋爱的“矛盾审计”1.1 霍普博士的实验在做什么题目背景讲的是教授观察一群虫子。具体输入是这样第一行一个整数T表示测试数据的组数。每组数据先给两个数n和mn是虫子的数量m是观察到的互动记录条数。接下来m行每行两个整数u和v表示编号为u和v的两只虫子发生了交配行为。在正常的自然规律下交配只能发生在异性之间。所以每一条记录都像一个断言u和v必须是异性。题目问的是这些断言放在一起会不会自相矛盾如果哪两只虫子根据之前记录已经被推断成同性后面又出现一条记录说它俩发生了交配那就说明这批虫子出现了可疑情况——即可能存在同性的行为。这时输出 Suspicious bugs found!否则输出 No suspicious bugs found.这句话值得再拆一遍。“异性”是这道题里唯一的关系类型但两条异性关系通过传递可以推出同性关系。比如1和2是异性2和3也是异性那么1和3一定同性。如果此时又给一条“1和3交配”的记录矛盾就出现了。这个传递过程正是并查集擅长处理的东西。换一种说法每行输入就是一个关系方程方程的内容是“u的性别和v的性别不同”。1.2 一个能跑通的手算例子拿最简单的n3、m3来试。输入三行1 22 31 3。处理第一条1和2建立异性关系处理第二条2和3建立异性关系由此我们已经能够推出1和3是同性第三条却要求1和3是异性直接冲突。所以输出Suspicious bugs found。如果用数学语言描述每只虫子就是一个布尔变量0代表某一种性别1代表另一种性别。“u和v交配”就是要求变量u和变量v取值不同。现在给出一组形如“u xor v 1”的方程问方程组是否可解。这就是这道题真正的数学模型。顺便注意一个细节题目里n的上限并不大但是m可能比较大所以算法必须做到接近线性不能用 O(n^2) 的枚举判断这也是为什么并查集是这里的标准解法。1.3 输入输出里的那些小陷阱POJ 老平台的输出格式非常严格。样例输出长这样Scenario #1: Suspicious bugs found! Scenario #2: No suspicious bugs found.注意每个Scenario序号从1开始序号后是冒号Suspicious...以感叹号结尾No suspicious...以句号结尾两组输出之间还有一个空行。写代码的时候最好直接照抄样例连空格都不要改不然很容易拿到Presentation Error。另外每组数据之前都要重新初始化并查集数组。这个问题说起来不值一提但真到比赛或者笔试现场紧张起来很容易漏一旦漏了上一组的残留关系会直接污染当前组的判断调试起来又隐蔽又费时间。2. 从“一个集合”到“一条边”普通并查集为什么不够用2.1 基础并查集只管“是否同伙”普通并查集能做的只有一件事把若干元素合并成若干个集合并回答任意两个元素当前是否在同一个集合里。它的世界里没有“关系”这个维度。对于这道题我们需要的不仅仅是“1和2有没有关系”还需要知道“1和2到底是不是异性”。同一个集合里的元素并不代表一定是同性恰恰相反在一堆“异性”约束下同一个集合里应该存在两种性别阵营。这就暴露了基础并查集的能力边界它可以告诉你两个人是否被约束链条连在了一起但无法告诉你沿着链条走过去之后两个人的关系到底是什么。而题目偏偏要的是后者。打个比方普通并查集只能告诉你“这两位确实认识”带权并查集却能告诉你“这两位是朋友还是对手”。2.2 补集法先绕开权值也能AC很多人第一次做这道题用的是“补集法”也叫种类并查集。思路很巧妙把数组开到2n编号i代表“i这号虫子”编号in代表“与i性别不同的那一类虫子”。对于每条输入u v它表明u和v是异性。处理方式如下int find(int x) { return fa[x] x ? x : (fa[x] find(fa[x])); } void unite(int a, int b) { int x find(a), y find(b); if (x ! y) fa[x] y; } bool same(int a, int b) { return find(a) find(b); } if (same(u, v)) { bad true; } else { unite(u, v n); // u 和 v 的异类同阵营 unite(v, u n); // v 和 u 的异类同阵营 }这段代码的含义是既然u和v不同性别那么u必然和“v的异性群体”是同一性别v也必然和“u的异性群体”是同一性别。如果某次判断时发现u和v已经处于同一个集合说明前面的推导已经认定它俩是同性了矛盾。补集法代码很短能AC很多题解也这么写。但它本质上是把“关系”这个标签编码进了集合编号里。一旦关系的种类从2种变成3种、4种比如经典的“食物链”题补集法的数组就要开n*k那么大逻辑也会瞬间变得混乱。2.3 带权并查集把关系挂在边上带权并查集换了一个思路集合还是那个集合但每个元素到父节点之间多了一个权值。这个权值记录了两者之间的关系。对于本题权值只有两个取值0表示“和父节点同性”1表示“和父节点异性”。这样一来任意两个元素之间的关系都可以通过路径上的权值合成出来。形象一点说普通并查集只给你一张“谁和谁连着”的拓扑图带权并查集则给每条父子之间的边都涂了颜色红色代表同类、蓝色代表异类。查询时沿着路径把颜色“叠加”起来就能知道端点的真实关系。因为本题关系只有两种这个叠加运算恰好就是异或。为什么是异或而不是加法因为“相同/不同”本身就是二元关系两个二元关系拼接后仍然只有两种结果。“同性 拼 异性”得到异性“异性 拼 异性”得到同性这正好是二进制异或的规则。有了这个直觉下面的公式推导就很自然了。3. 带权并查集的数学基础一条路径一个异或3.1 权值约定与主递归结构设 fa[x] 是 x 的父节点rel[x] 是 x 与 fa[x] 的关系0表示同性1表示异性。初始时每个虫子独立fa[x]xrel[x]0。find 函数的作用是找到根并且在找根的过程中把路径压缩掉。路径压缩之后x 的父节点直接变成根rel[x] 也必须随之更新成“x与根的关系”。更新的方法很自然先递归找到根的 rel 信息再把“x与旧父节点的关系”和“旧父节点与根的关系”异或起来。3.2 路径压缩的代码为什么必须存旧父节点下面是最容易写错的地方。看这段代码int find(int x) { if (fa[x] x) return x; int p fa[x]; int root find(p); rel[x] ^ rel[p]; return fa[x] root; }关键在第二行先把当前的父节点存进 p。因为递归调用 find(p) 之后fa[x] 已经被改成了根节点而 rel[根] 是0如果此时写 rel[x] ^ rel[fa[x]]等于异或0旧父节点的关系就丢失了所有信息都会报废。递归返回后p 的 rel 已经是“p与根的关系”此时再执行 rel[x] ^ rel[p]恰好等于 x与p的关系 异或 p与根的关系也就是 x与根的关系。最后 fa[x]root 完成路径压缩。很多人在这一步翻车就是因为没有意识到递归里的副作用会覆盖 fa[x]。写带权并查集时我建议永远先保存旧父节点这也算一条铁律。3.3 合并两个集合根与根的关系怎么算假设现在输入一条记录 u v表示 u 和 v 异性。先分别 find(u) 和 find(v)得到两个根 fu、fv以及 rel[u]u与fu的关系、rel[v]v与fv的关系。如果 fu≠fv说明两个集合还没有关联需要把其中一个根挂到另一个根下面。把 fu 挂到 fv 下面后要填的就是 rel[fu]也就是 fu 与 fv 的关系。路径是这样的fu - u 的关系是 rel[u] u - v 的关系是 1 v - fv 的关系是 rel[v]把三段关系依次异或起来就得到 fu 与 fv 的关系rel[fu] rel[u] ^ 1 ^ rel[v]这里用到的路径合成本质上是向量叠加整条路径的关系等于每一段上的关系异或和。因为路径压缩已经把 u、v 到各自根的关系全部收拢好了所以公式可以直接写出来。再手算一个例子。初始三只虫子1、2、3都独立。处理(1,2)find(1)1, find(2)2rel[1]0rel[2]0把1挂到2下面rel[1] 0^1^0 1表示1和2异性。处理(2,3)find(2)2find(3)3把2挂到3下面rel[2]0^1^01表示2和3异性。这时候树变成 1-2-3rel[1]1rel[2]1。再看(1,3)find(1)路径压缩后 rel[1] 1^1 01和3同性find(3)3rel[3]0两个根相同执行矛盾判断rel[1]^rel[3] 0不等于1所以矛盾。这和前面手算结果一致。3.4 同集合内的判断公式如果 find(u) 和 find(v) 返回同一个根说明 u 和 v 已经在同一棵树上我们能够直接推算出它俩应有的关系。计算方法同样是路径合成u - fu 的关系是 rel[u] fu fvfv - v 的关系是 rel[v] 所以 u - v 的关系 rel[u] ^ rel[v]题目输入要求 u 和 v 是异性也就是期望关系等于1。如果算出来不是1说明出现了矛盾把 bad 标记置为 true。需要强调的是这里的 rel 是路径压缩后的值必须保证 find(u) 已经执行过否则拿到的 rel[u] 可能只是到旧父节点的关系判断就会出错。3.5 操作公式小结为了方便记住整理成一张表。操作触发条件公式路径压缩find(x) 递归返回rel[x] rel[x] ^ rel[旧父节点]合并两个集合find(u) 和 find(v) 根不同rel[fu] rel[u] ^ 1 ^ rel[v]判断是否矛盾find(u) 和 find(v) 根相同若 rel[u] ^ rel[v] ! 1则矛盾看完这张表你可能会发现整道题其实只涉及一个核心运算异或。理解了路径合成就理解了带权并查集其他都是套壳。4. 完整代码与踩坑复盘从推导到 AC4.1 可直接提交的C代码这篇代码以 C98 的风格写头文件只用了 cstdio 和 cstring老OJ也能编译。数组大小多开一些避免因为边界记混而越界代价可以忽略。#include cstdio #include cstring const int MAXN 100005; int fa[MAXN], rel[MAXN]; // rel[x] 0 表示 x 与 fa[x] 同性 // rel[x] 1 表示 x 与 fa[x] 异性 int find(int x) { if (fa[x] x) return x; int p fa[x]; int root find(p); rel[x] ^ rel[p]; return fa[x] root; } void init(int n) { for (int i 1; i n; i) { fa[i] i; rel[i] 0; } } int main() { int T, n, m; scanf(%d, T); for (int kase 1; kase T; kase) { scanf(%d%d, n, m); init(n); bool bad false; for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); if (bad) continue; // 已经矛盾但必须继续读掉数据 int fu find(u); int fv find(v); if (fu fv) { if ((rel[u] ^ rel[v]) ! 1) bad true; } else { fa[fu] fv; rel[fu] rel[u] ^ 1 ^ rel[v]; } } printf(Scenario #%d:\n, kase); if (bad) printf(Suspicious bugs found!\n); else printf(No suspicious bugs found.\n); printf(\n); } return 0; }代码里的关键点都写了注释。接下来把这些坑一个个复盘我踩过其中大部分。4.2 踩坑一发现矛盾就 break结果后续输入错位新手最常犯的错误是一旦 bad 变 true直接在循环里 break。这会让后面本应读入的 u、v 残留在输入缓冲区下一组测试数据一上来就读取错位整个程序的后续输出全部错乱。正确做法是像代码里那样先 scanf 把数据读进来再判断 bad 并 continue。已经矛盾的情况下无需再更新并查集但读入动作不能省。这个问题在本地小样例上很难暴露一旦遇到多组数据的边界case排查起来相当折磨。4.3 踩坑二find 里的更新顺序find 的递归写法容易出问题已在3.2节详述。再补充一句如果用非递归路径压缩必须先把整条路径上的节点记录下来再从根向叶子反向更新 rel代码反而更复杂。竞赛里递归写法完全够用不要为了炫技换非递归。我也见过有人把递归写成了if (fa[x] ! x) { fa[x] find(fa[x]); rel[x] ^ rel[fa[x]]; } return fa[x];这个写法在 C 求值顺序上非常危险因为 fa[x] 在赋值语句左边已经被改掉右边的 rel[fa[x]] 拿到的可能是根节点自己的 rel恰好又是0。这种 bug 不是每次必现而是和递归顺序强相关最难调。4.4 踩坑三输出格式导致的无谓罚时POJ 对输出极敏感。Suspicious 那句以感叹号结尾No suspicious 那句以句号结尾Scenario 序号从1开始两组数据之间还要有一个空行。这些细节直接照抄题面样例提交前最好和自己本地运行结果逐字比对。遇到过有人算法全对却因为多打了一个空格反复 PE非常影响心态。老平台判题细致宁可多检查一遍输出也不要赌它宽松。4.5 踩坑四初始化不及时每组数据开始前 init(n) 是必须的。曾见过有人把 init 放在最外层只执行一次第二组数据开始后所有 find 都变成死循环或者误判。如果发现答案呈现“第一组对、后面全乱”的规律先检查初始化。另一个容易被忽略的细节是如果 n 在当前测试组比上一组大fa 和 rel 里新下标位置可能残留旧值所以 init 的循环一定到本组 n不能只清到上次的 n。4.6 复杂度表现与稳定性用了路径压缩之后find 的均摊复杂度接近常数。整体复杂度是 O((nm)α(n))空间是 O(n)。即使 m 到百万量级也能轻松跑完。如果需要更稳定可以在合并时维护树高做按秩合并但本题数据规模不大不写也能过。我个人的习惯是先保证正确性再考虑常数优化竞赛场上正确性永远排在第一位。5. 从虫子到食物链再到奇偶区间关系并查集到底能套多远5.1 它本质上是一道二分图判定把所有虫子看成图的顶点每条交配记录看成一条无向边题目要求每条边两端颜色不同且颜色只有两种。这不就是标准的二分图判定吗离线做法是 BFS 染色遇到已经着色且与当前期望冲突的边说明不是二分图。vectorint g[MAXN]; int color[MAXN]; // -1 表示未染色 bool bfs(int s) { queueint q; q.push(s); color[s] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (color[v] -1) { color[v] color[u] ^ 1; q.push(v); } else if (color[v] color[u]) { return false; } } } return true; }染色法同样能AC但需要把所有边存下来且对所有连通分量都调用一遍。相比之下带权并查集是边读入边判断的在线做法不需要存图代码也更短。两种方法对比能加深对“关系传递”的理解二分图问题只是二元关系的特例带权并查集是站在关系代数的更高视角做题。5.2 从二元关系到多元关系食物链当关系种类从两种变成三种时异或就不够用了。经典的 POJ 1182 食物链三种动物之间存在同类、吃、被吃三种关系这是一个模3循环关系。带权并查集的思路依然成立只是 rel 的含义变成0/1/2路径压缩时用 (rel[x] rel[p]) % 3合并和判断公式也变成模3加减法。所以不要死记异或公式要理解“关系沿路径叠加”的通用想法。二元关系恰好是模2运算因此退化成异或多元关系就是模k运算。把这道虫子题吃透再去写食物链你会发现只是把“异或”换成“模3加法”框架完全不动。5.3 从点关系到区间关系奇偶性问题还有一类题目把数组下标当成并查集的点把区间的性质建模成两个前缀点之间的关系。比如区间奇偶性判断输入 l r parity表示 sum(l..r) 的奇偶性。令前缀数组 pre则 pre[r] 与 pre[l-1] 的异或值就是这个奇偶性。这样一次输入就变成了两个前缀点之间的一个关系约束完全可以用带权并查集处理。区间范围通常很大还需要先做离散化。这类题目看起来和虫子毫无关系但底层的“关系方程判断矛盾”模型是完全一样的。5.4 什么时候毫不犹豫选带权并查集我的判断标准有三条题目给出的是元素之间的二元或 k 元关系关系可以定义出明确的“叠加”运算需要在线判断多组约束是否矛盾。满足这三条就可以考虑带权并查集。如果题目只要求判断连通性普通并查集就够如果关系种类复杂到没法叠加可能需要另想建模。刷题时遇到 POJ 2492 这样的题目最大的价值不在于背住一个公式而在于理解“并查集并的到底是什么”。它可以是一个连通块也可以是一张带标签的关系网标签的叠加方式就是算法的核心。我自己刷这道题时最大的收获不是记下了 rel[fu] rel[u] ^ 1 ^ rel[v] 这个式子而是养成了一个习惯看到“给出一堆元素间的关系约束判断是否矛盾”这种题目先想想关系能不能定义成路径叠加。能就用带权并查集不能再考虑其他建模。后来做食物链、奇偶区间、火车调度这些题我都能很快套上同一套框架。如果你正在学带权并查集建议把这道题独立写一遍然后用纸笔把3.3节那个路径合成图自己推一遍再试着自己把 rel 数组的语义改成“同类/异类”之外的其他二元关系。推通了这一步你的并查集水平会明显上一个台阶。