如果你带过刷《信息学奥赛一本通》的学生大概率会被问同一个问题P1385这道“团伙(group)”为什么敌人的敌人是朋友这题看着像脑筋急转弯实际上是一道非常经典的并查集建模题。我第一次带集训队的时候也在这上面卡过——不是不会写并查集而是不知道怎么把“敌人”这种负向关系塞进一个只会合并同类的数据结构里。后来想通了反集也叫扩展域这套思路再看题目就完全透明了。这篇文章我从建模开始把两种主流的写法、容易踩的坑、以及怎么验证你的实现是正确的一次讲清楚。新手可以直接照抄代码老手可以重点看第四节和第五节的边界讨论。1. 先别急着写代码把题目的三条规则读透1.1 题目在讲什么P1385团伙的题面不长大意是有n个人编号1到n现在有m条关系描述。每条描述形如“F p q”或“E p q”F表示p和q是朋友E表示p和q是敌人。然后题目给了两条硬性规则朋友的朋友是朋友这条具有传递性。敌人的敌人是朋友这是题面给定的规则不是脑筋急转弯。目标把这些人分成若干组每组内任意两个人之间都必须能通过朋友关系直接或间接相连问最多能分成多少个组。这里“最多”两个字很关键你要先理解为什么问最多。给定关系之后朋友关系是有传递性的如果a和b是朋友b和c是朋友那a和c也必须分进同一组这是硬性的不能拆。所以关系网一旦确定哪些人必须在一起其实是确定的。把必须在一起的人都并到一起剩下的集合就是组。在这个意义上分组结果其实是唯一的“最多”和“最少”没有区别。但题面用“最多”我理解是想强调我们要把朋友闭包尽量合并、不能随意拆散。你心里把这个当成“求朋友关系连通块个数”就行。1.2 “敌人的敌人是朋友”为什么会改变分组结果如果没有第二条规则这题就是普通的并查集F关系直接merge。第二条规则才是灵魂当一个敌人关系出现时它不仅告诉我们两个个体不是朋友还告诉我们在“另一个敌人”出现的时候几人之间的朋友关系会被触发。举一个最小的例子。三个人甲乙丙。甲和乙是敌人乙和丙是敌人。根据规则2甲和丙就是朋友。三个人里甲和丙必须同组而乙跟甲、乙跟丙都是敌人不能同组所以最少需要两组乙单独一组甲丙一组。如果不用并查集手动推三个人还行推一百个人、几百条关系就彻底乱了。这正是需要数据结构的原因关系之间的连锁推导最有资格的就是并查集因为它的专长就是把“传递性”变成接近O(1)的查找。你可能会想既然朋友关系是传递的那我把所有朋友关系建图跑BFS求连通块行不行行但每加一条关系可能都要重建图或增量更新复杂度不划算。并查集的优雅之处在于它用一棵树把所有传递关系压缩成了“查根”这一个操作。1.3 亲手画一遍关系推演这里用一个稍微扩展的例子。假设5个人关系E 1 2E 2 3F 3 4问最终几组一步一步推E 1 21和2是敌人。E 2 32和3是敌人。因为1和2是敌人、2和3是敌人所以1和3成为朋友。注意这条朋友关系是规则2推出来的不是输入直接给的。F 3 43和4是朋友。由1和3是朋友、3和4是朋友推出1、3、4同组。2和任何人都是敌人单独一组。5没有任何关系单独一组。最终答案3组{1,3,4}、{2}、{5}。你现在可以试着用暴力模拟一下这个推演会发现“E 1 2”和“E 2 3”这两条数据在推演中通过“敌人-敌人-朋友”搭了一座桥。这个桥就是后面并查集建模要解决的核心问题。很多人卡在这道题不是不会并查集而是没有意识到敌人关系本身不能直接merge但敌人关系带来的间接朋友关系必须merge。2. 核心建模怎么把“敌人关系”装进并查集2.1 并查集只认“同类”这是好事还是坏事并查集的本质就一句话把元素按“属于同一个集合”的关系合并。朋友关系天然是同类关系直接merge没有问题。敌人关系是“不同类”并查集本身不支持“把两个元素标为不同组”。很多初学者卡就卡在这并查集只能告诉你两个元素在不在同一组不能直接告诉你两个元素“不能在同一组”。但是别忘了题目给了隐藏条件敌人的敌人是朋友。所以敌人关系不是孤立的它是通过“共同的敌人”来间接制造朋友关系的。换句话说我们完全可以把“敌人的敌人”关系显式地建模成朋友关系而不去直接处理“敌人”关系本身。这个“转化”的过程就是本题的建模核心。2.2 反集扩展域的设计直觉既然并查集管不了“敌人”那我们就为“敌人”也开一个集合。具体来说对于每个编号i再造一个虚拟编号in用它代表“i的敌人所属的集合”。这样整个并查集的元素数量就是2n。i自己1到ni的敌人集合n1到nn当输入说“p和q是敌人”时做两件事把p并入“q的敌人集合”即merge(p, qn)把q并入“p的敌人集合”即merge(q, pn)为什么这样做就够了因为“q的敌人集合”会一直累积所有被宣布为“q的敌人”的人都会merge到qn这个集合里。于是两个同时和q为敌的人p、r就都出现在qn这个集合里。他们俩因此被并查集判定为同类——这正是规则2要求的“敌人的敌人是朋友”。这里有个容易绕晕的点merge(p, qn)并不是说p变成了q的敌人集合的代表元素而是说p这个节点加入了qn所在的集合。之后如果又有一个r也被merge到qnp和r的根就相同了。敌人域节点在这里充当了一个“公共敌人联络点”的角色所有跟q结仇的人都挂到同一个联络点上自然就互相连通了。2.3 用3人例子验证反集继续用甲乙丙的例子E 1 2、E 2 3。假设n5只是为了下标方便E 1 2merge(1, 7)merge(2, 6)E 2 3merge(2, 8)merge(3, 7)现在看1和31在7所在的集合里第一次合并时被并了进去3也在7所在的集合里第二次合并时被并了进去。所以1和3同根朋友关系成立。而2自己呢2和1、3并没有直接merge过2的根和它们的根不同敌人关系保持。完美符合规则推演。所以你可以把in理解成一个“敌营集合”的容器所有和i结过仇的人都会被扔进这个容器容器里的人彼此都成了朋友。这是理解扩展域并查集的关键画面。3. 两种主流写法两倍数组版和enemy数组版3.1 写法一两倍数组扩展域完整C代码#include bits/stdc.h using namespace std; const int MAXN 2005; // 实际需要 2*nn 一般不超过 1000 int fa[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void merge(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) fa[ra] rb; } int main() { int n, m; cin n m; for (int i 1; i 2 * n; i) fa[i] i; // 注意是 2n不是 n while (m--) { char op; int p, q; cin op p q; if (op F) { merge(p, q); } else { // op E merge(p, q n); merge(q, p n); } } int ans 0; bool used[MAXN] {false}; for (int i 1; i n; i) { int r find(i); if (!used[r]) { used[r] true; ans; } } cout ans endl; return 0; }关键点三个。第一初始化必须从1循环到2n。只初始化到n的话遇到E操作访问qnfind里面fa[x]是个垃圾值轻则结果错重则数组越界崩溃。第二合并时顺序无所谓merge(p, qn)和merge(q, pn)两条都要写少一条都会漏掉“敌人的敌人是朋友”的一半推导。第三统计时用used数组给根打标记。注意i从1到n但find(i)的结果可能落在n1到2n区间敌人域节点也可以成为某个人的根所以used数组必须开2n1。这一点非常容易挂后面第五部分专门说。3.2 写法二enemy数组反集思路是维护一个enemy数组enemy[i]记录“i当前已知的某一个敌人”。当再次发现i有新的敌人j时因为“敌人的敌人是朋友”所以j和enemy[i]是朋友合并它们。#include bits/stdc.h using namespace std; const int MAXN 1005; int fa[MAXN]; int enemy[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void merge(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) fa[ra] rb; } int main() { int n, m; cin n m; for (int i 1; i n; i) fa[i] i; memset(enemy, 0, sizeof(enemy)); while (m--) { char op; int p, q; cin op p q; if (op F) { merge(p, q); } else { if (enemy[p] 0) enemy[p] q; else merge(q, enemy[p]); if (enemy[q] 0) enemy[q] p; else merge(p, enemy[q]); } } int ans 0; bool used[MAXN] {false}; for (int i 1; i n; i) { int r find(i); if (!used[r]) { used[r] true; ans; } } cout ans endl; return 0; }这版的好处是空间只要n级别坏处是逻辑分支多容易写漏。比如E p q时你要同时处理p的敌人列表和q的敌人列表两边都要检查enemy[p]和enemy[q]。第一次接触建议先掌握两倍数组版思路更直白代码更不容易错。等两倍数组版吃透了再回头写这个版本你会发现它其实是扩展域写法的一种空间优化enemy[i]记录的“某一个敌人”本质上就是i的敌人域的一个代表。3.3 两种写法对比对比维度两倍数组扩展域enemy数组反集空间2n1n1合并逻辑统一E操作就是两次merge分支多需维护enemy数组理解成本中需要接受“敌人域”概念中需要想通“第一个敌人”记录写错概率低中等容易漏某一边拓展性强适合食物链等多维关系题弱只适合二元敌对关系我的建议是考试时用你有把握的写法。平时练习两种都要写一遍因为后面的题目会用到扩展域思想变体。如果你在信息学奥赛一本通配套OJ提交注意看题目要求是否需要文件读写部分题库版本会用文件输入输出。4. 统计分组与边界处理4.1 为什么必须find(i)而不是fa[i]这是新手最容易错的地方。统计时如果直接数fa[i]里有多少个不同的值会漏掉那些“经过了路径压缩但fa[i]不是根”的节点。比如merge(3,5)之后如果5作为根fa[3]5但如果后来又merge(5,7)且7成为根fa[3]可能还是5没有路径压缩到7。这时直接看fa[3]和fa[5]会认为3和5不同组但实际上它们是同一组。所以统计分组的标准写法就是对所有i属于1到n执行find(i)把得到的根放进一个去重容器里。最简单就是bool数组标记。这也是很多题解里那行ans的原理。同样的道理在处理输入过程中凡是判断两个元素是否同组也一律用find(a)find(b)绝对不要用fa[a]fa[b]。路径压缩是并查集的灵魂但你得配合find来用。4.2 孤立点、重复关系、先敌后友孤立点一个人如果从头到尾没出现在任何关系里它自己就是一组。初始化fa[i]i之后统计时自然算一组不用特殊处理。重复关系输入里可能出现两次“F 1 2”。merge两次不会改变结果并查集天然幂等不用单独判重。先敌后友比如先E 1 2后F 1 2。这属于逻辑矛盾的数据一般OJ题面不会出现因为“朋友”与“敌人”不能同时成立。如果你自测时遇到这种数据以正规竞赛题的标准这类数据不在测试范围内。如果真要在业务系统里处理这种冲突需要额外的校验逻辑那就不是这道题要考虑的了。但你可以想一想如果数据保证无矛盾并查集统计出来的连通块必然不会同时包含敌人关系这是判断实现正确性的重要依据。4.3 复杂度分析并查集加路径压缩后单次find的均摊复杂度接近O(α(n))α(n)是反阿克曼函数增长极慢实践中可以认为是常数级别。本题m条关系每条关系做常数次merge总复杂度O((nm)α(n))。n和m在本题范围下跑起来毫无压力哪怕是n到几万、m到几十万这个复杂度也完全够用。这也是为什么这类“关系传递”题几乎无脑选并查集的原因。5. 我在这道题上踩过的坑5.1 字符读入的坑题目输入是“F 1 2”这种字符后面有空格。用cin op自动跳过空白字符没问题。但如果你自测时用getchar或者scanf(%c)很容易把换行符读进来。我当年第一次用scanf(%c,op)结果op总是读到空格或换行程序行为全乱。正确姿势是scanf( %c, op)%c前面加一个空格吃掉空白。用cin最省心。5.2 初始化范围写错两倍数组版初始化必须从1循环到2n。我见过很多新手只初始化到n结果一跑就崩。因为输入E操作时会访问qnn1到2n这些下标如果没初始化find里面fa[x]可能是垃圾值或者下标越界。这类问题在OJ上报什么错都有可能有时候是RE有时候是莫名其妙的WA排查起来很头疼。5.3 统计容器下标开小前面说了统计时bool数组要开到2n1才行。如果沿用n1的数组当某个人的根落在n1到2n区间时在扩展域写法中完全可能比如一个孤立的敌人域节点成了某个人的根就会数组越界行为不可预测。实际验证一下n2只有一条关系“E 1 2”。扩展域执行后find(1)4find(2)3两个根都大于2。如果bool数组只开到3访问used[4]就是越界。在这个例子里程序可能碰巧没崩但统计结果已经不可信了。我见过学员在这上面排查了半小时最后发现数组开小了一格。5.4 验证方法自己造小数据对拍写完代码别只看样例过了就提交。我通常会让学员自己造几组小数据手动推演答案再和程序输出对比。比如n3的所有关系组合或者用脚本暴力枚举。对拍脚本的逻辑不复杂写另一个暴力程序直接维护朋友关系图每来一条关系就更新图的闭包最后统计连通块个数两个程序在同一份随机数据下输出必须完全一致。暴力程序甚至不需要用并查集直接维护一个邻接矩阵来一条朋友关系就做一次Floyd式的闭包更新n小的时候完全可行。这种对拍习惯比看一百篇题解都有用它在训练你“用另一个思考路径验证同一个结论”的能力。6. 举一反三关系判断题的通用模型6.1 同类题目一览这道题的建模思想在竞赛里非常常见洛谷P1892 团伙和本题一模一样可以用来验证代码。洛谷P2024 食物链三种关系的扩展域并查集是本题的加强版。每个人不仅有“同类域”还有“捕食域”和“天敌域”域的数量从2个变成3个。NOIP 2010 关押罪犯需要按仇恨值从大到小处理用扩展域判断矛盾条件是反集在贪心加并查集里的经典应用。很多“朋友的朋友是朋友”类思维题都脱胎于这套模型。学会P1385之后去看P2024食物链会顺畅很多因为“敌人的敌人是朋友”和“天敌的天敌是猎物”本质上都是给每个实体开多个虚拟域在不同域之间连边。6.2 从这道题提炼的思维套路以后再遇到“关系传递”“矛盾判定”“分组计数”这类问题脑子里的第一反应可以是能不能用并查集如果能那么正向关系直接merge反向关系建一个虚拟域再merge。具体分几步明确有哪些“实体维度”比如自己、敌人、捕食者、天敌。每个维度开一组节点总节点数等于实体数乘以维度数。把输入的每条关系翻译成对应维度节点之间的merge。最后按需要统计或判断矛盾。这个套路熟练之后这类题对你来说就是送分题。我个人在教学时有个习惯凡是学生卡在团伙这道题都会让他们先手动推三人敌-敌-友的例子把“2n这个集合是干嘛的”在纸上画出来再回来看代码。这一步想通了后面食物链就是同一套思路换几个维度名而已。最后再分享一个小技巧如果你实在不确定初始化边界数组开大一点本题2n最多也就两千左右开成5000甚至10000都不会有事空间不敏感但初始化循环和used数组别忘了跟着开大。数组宁可多开一百不要少开一格。