刷题刷到信息学奥赛一本通 1385或者洛谷 P1892 的时候很多人的第一反应是这题不就是并查集吗然后顺着模板敲完样例一跑过了交上去WA。问题几乎都出在同一个地方题目里那句我敌人的敌人也是我的朋友。这句话看起来只是多了一个简单的传递规则但它不是朋友链那种顺着合并就能搞定的逻辑。我第一次做这题也是在并查集上死磕了很久后来才明白这道题要的不是普通并查集而是并查集的一个经典变式反集。这篇文章就把这道题的完整思路、推导过程、AC 代码以及我在实战中踩过的坑从头到尾讲一遍适合刚学完并查集、想找典型例题加深理解的 OIer。1. 题目到底在说什么1.1 原题关键条件逐条拆解题目是 BOI2003 的原题后来被收录进信息学奥赛一本通题号 1385洛谷题号 P1892。题目背景是强盗团伙但我们做算法题时可以简单理解为人和团伙就行了。题面给出 n 个人编号从 1 到 n。然后给你 m 条已知关系每行一个字符 F 或 E后面跟着两个编号 a 和 b。F 表示 a 和 b 是朋友E 表示 a 和 b 是敌人。除此之外还有两条硬性规则我朋友的朋友是我的朋友。我敌人的敌人也是我的朋友。最后要求的是这 n 个人最多能分成多少个团伙。同一个团伙里的人任意两个人都必须是朋友关系。数据范围我记得很清楚n 不超过 1000m 不超过 5000。这个范围其实意味着就算你写一个 O(n^2) 的暴力也不是完全不能跑但它作为教材题想考察的显然是并查集这种规范的数据结构而且不是最基础的模板并查集必须想办法处理敌人关系这个额外维度。输入输出格式上洛谷和一本通完全一致第一行 n第二行 m接下来 m 行才是关系。输出一个整数表示最多团伙数。1.2 最多团伙数到底在问什么很多同学对题面里最多这个词有疑惑。朋友关系满足三个性质自反、对称、传递。A 和 B 是朋友B 和 C 是朋友那么 A 和 C 一定可以通过朋友链成为朋友。这本质上就是离散数学里的等价关系。等价关系会把集合划分成若干个等价类每个等价类内部任意两人互相可达不同等价类之间没有朋友边相连。放到这道题里每个等价类就是一个团伙。团伙的划分其实是由朋友关系唯一确定的不是我们想拆就能拆的。题目说最多只是因为如果有两个人既没有朋友关系链、也没有敌人关系牵连他们天然就属于两个团伙而两个团伙的人数可以自由分配。所以分析到最后最多团伙数就是在问在朋友关系和敌人的敌人是朋友这两条规则的作用下n 个人最终会形成多少个极大连通块。1.3 先把样例手工推一遍洛谷 P1892 的样例是这样的6 4 E 1 4 F 3 5 F 4 6 E 1 2一共有 6 个人4 条关系。朋友关系是 3 和 5、4 和 6敌人关系是 1 和 4、1 和 2。从敌人关系出发1 的敌人有两个4 和 2。根据我敌人的敌人也是我的朋友4 和 2 就成了朋友。而 4 又和 6 是朋友所以 2、4、6 三个人在一个团伙里。再看 3 和 5他们是直接朋友关系构成一个团伙。最后是 1。1 和 4、2 都是敌人没法进 {2,4,6} 那个团伙1 也没有别的朋友关系所以 1 单独一个团伙。答案就是 3 个团伙{2,4,6}、{3,5}、{1}。手工推很简单难的是怎么让程序也这么自觉地推出 4 和 2 是朋友。这就引出下面的核心问题。2. 为什么普通并查集不够用反集怎么解决2.1 普通并查集只能表达同类合并并查集能做的操作归根到底就两个把两个元素并入同一个集合查询两个元素是否在同一个集合。它天然适合朋友的朋友是朋友这种传递关系因为朋友关系和连通块完全同构。但面对敌人的敌人是朋友普通并查集缺的是一套表达对立的机制。如果你在遇到 E 的时候天真地把 a 和 b 合并那逻辑上就变成了敌人也是朋友显然错了。如果你遇到 E 时什么也不做那又无法体现敌人的敌人是朋友这个传递规则。打个比方普通并查集像是一本班级花名册只记录了谁和谁同班但没有记录谁和谁绝对不能同班。这道题需要同时维护两层信息朋友关系和敌对关系并且敌对关系会反向推动朋友集合的合并。2.2 反集的核心设计一个人占两个位置反集的做法非常巧妙把并查集的空间开成 2n。1 到 n 是每个人的本体n1 到 2n 是每个人的敌人集合代表。更准确地说对于人 ii 所在的集合表示i 的朋友集合in 所在的集合表示i 的所有敌人的集合。注意in 不是一个真人而是一个虚拟节点它专门用来收集哪些人和 i 有仇。当题目告诉你 a 和 b 是敌人时我们做两件事把 b 并到 a 的敌人集合里merge(b, an)把 a 并到 b 的敌人集合里merge(a, bn)这样设计之后任意两个人都可以通过各自的敌人阵营产生间接联系。同时敌人关系本身并没有让 a 和 b 出现在同一个朋友集合里a 和 b 依然不是朋友符合题意。这个方法在很多资料里叫反集或补集。它的思想本质上是用空间换逻辑多开一倍空间给每个人安排一个影子位置专门收纳敌人。2.3 为什么两条 merge 能实现敌人的敌人是朋友假设有三个人 a、b、c已知 a 和 b 是敌人a 和 c 也是敌人。按上面的规则处理a 和 b 是敌人时执行 merge(b, an) 和 merge(a, bn)。其中 merge(b, an) 这一步把 b 放进了 a 的敌人阵营。处理a 和 c 是敌人时同样执行 merge(c, an) 和 merge(a, cn)。此时 c 也进入了 a 的敌人阵营。现在 b 和 c 都在 an 这个集合里所以 b 和 c 自动成为同一个朋友集合里的人。全程没有任何一步在主动 merge(b, c)但通过共同的 anb 和 c 的关系被完全打通了。这就是我敌人的敌人也是我的朋友的并查集翻译版本。反集之所以经典就是因为它用额外一倍空间换来了对对立关系的建模能力。3. 完整代码实现从初始化到统计团伙数3.1 并查集基础函数与初始化先写并查集的基础函数。因为 n 很小普通的递归 find 完全够用但我在写这类题时习惯用迭代加路径压缩顺便展示一个更通用的写法。#include bits/stdc.h using namespace std; const int MAXN 2005; int fa[MAXN]; int find(int x) { int root x; while (fa[root] ! root) { root fa[root]; } while (x ! root) { int nxt fa[x]; fa[x] root; x nxt; } return root; } void merge(int x, int y) { int fx find(x); int fy find(y); if (fx ! fy) { // 小号优先让根尽量落在编号小的节点上 if (fx fy) swap(fx, fy); fa[fy] fx; } }这里的 merge 我特意写成了小号优先。为什么因为补集节点的编号在 n1 到 2n本体节点编号在 1 到 n。只要某个集合里存在本体节点按小号优先合并根就更倾向于落到本体节点上。这样最后用find(i) i统计答案时不容易踩坑。这个细节我后面会专门讲。初始化部分不要漏for (int i 1; i 2 * n; i) { fa[i] i; }数组至少要开到 2n 1防止访问越界。3.2 主函数逻辑两种关系的不同处理主函数的核心就是读入每条关系然后分类处理int main() { int n, m; cin n m; for (int i 1; i 2 * n; i) { fa[i] i; } for (int i 1; i m; i) { char op; int a, b; cin op a b; if (op F) { merge(a, b); // 朋友关系直接合并 } else { merge(a n, b); // b 进入 a 的敌人阵营 merge(b n, a); // a 进入 b 的敌人阵营 } } int ans 0; for (int i 1; i n; i) { if (find(i) i) { ans; } } cout ans endl; return 0; }这段代码就是完整的 AC 代码。核心逻辑总共只有三种操作朋友直接合并敌人成对合并到对方的敌人阵营最后扫描本体节点统计团伙数。3.3 统计团伙数的两种写法统计答案有两种方式。第一种是上面这种扫描 1 到 n统计find(i) i的个数。它成立的前提是每个集合的根尽可能落在本体节点上也就是我们用了小号优先合并。第二种更稳妥直接借助 set 对根去重setint st; for (int i 1; i n; i) { st.insert(find(i)); } cout st.size() endl;为什么会有这种差异因为在并查集合并过程中根节点有可能会漂移到 n1 到 2n 这个补集区间。如果直接用find(i) i扫描 1 到 n就可能漏掉真正根在补集节点上的集合。set 写法不受根在哪个区间影响它就是直白地统计1 到 n 中每个人最终属于几个不同的朋友集合。所以如果你不想研究合并方向最稳妥的写法就是用 set。我在网上看过不少题解直接用f[i] i统计也能 AC多半是因为他们写出了小号优先这样的合并逻辑或者测试数据没有卡到根悬空的边界。我建议初学者直接上 set 写法然后把两种统计方式的原理都搞明白。3.4 把样例完整走一遍我们拿样例 6 4 来手动过一遍程序逻辑。初始化 fa[1] 到 fa[12]每个节点指向自己。第一条关系 E 1 4执行 merge(7, 4) 和 merge(10, 1)。此时 7 和 4 合并10 和 1 合并。注意 7 是 1 的敌人阵营10 是 4 的敌人阵营。第二条关系 F 3 5执行 merge(3, 5)3 和 5 合并。第三条关系 F 4 6执行 merge(4, 6)。这里 4 现在和 7 在同一个集合所以实际结果是 4、6、7 三个人所在的集合全部被打通。第四条关系 E 1 2执行 merge(7, 2) 和 merge(8, 1)。2 和 7 合并。由于 7 已经和 4、6 连通所以 2、4、6 成为一个朋友集合。1 则和 8、10 在一起。最后扫描 1 到 61 的根是 12 的根是 23 的根是 34 的根是 25 的根是 36 的根是 2find(i) i成立的有 1、2、3 三个节点答案 3和手工推导一致。这里能出现 find(2)2、find(3)3 这种理想局面正是因为合并时小号优先把根都压回了 2 和 3 这两个本体节点上。如果把合并方向写反比如总是让大号当根最后很可能会得到 7、10 这类补集根统计就会出错。4. 我实战中踩过的坑与排查过程4.1 只写一条 merge造成敌人的敌人没有生效我第一次做这道题时把敌人关系的处理写成了这样merge(a n, b);只做了把 b 丢进 a 的敌人阵营漏掉了对称方向的merge(b n, a)。样例一跑发现答案比预期大。我当时的排查方式是在每次 merge 之后把整个 fa 数组打印出来逐个集合观察。结果发现问题出在单向连接上a 进了 b 的敌人阵营但 b 没有进 a 的敌人阵营。这样一来当后面出现 a 的另一个敌人 c 时b 和 c 不一定能在同一个集合里相遇自然就无法推导出b 和 c 是朋友。这个坑让我彻底记住了反集的对称性。敌人关系是双向的两条 merge 必须成对出现缺一不可。之后我每次写这类题都会在心里默念一句敌人成双补集两边都要连。4.2 合并方向写反导致根悬空还有一次我把merge(a n, b)误写成了merge(b, a n)。从并查集的语义上来说两者其实是一样的都是把两个节点合并到一起。但问题是如果我的统计方式是find(i) i那么合并方向会影响最终根节点的位置。当时有个测试点 WA 了很久。我把数据打印出来后才发现某个团伙的根变成了补集节点比如 8 或者 11。而这个补集节点根本不在扫描范围内于是计数就少了 1。后来我总结出一个规律如果你用find(i) i统计就要在合并时统一小号优先如果你用的是 set 去重那合并方向随意写都行语义对就可以。两者选一个能省掉很多无谓的 debug 时间。4.3 字符读入和换行符的细节这道题的输入格式是每行开头一个字符。如果你用 scanf 读入要特别注意换行符的问题scanf(%c%d%d, op, a, b);这样直接写会在第一次读入时吞掉上一个换行符导致 op 变成回车。常见的处理方式是在 scanf 前面加一个 getchar()或者在格式串里加空格scanf(\n%c%d%d, op, a, b);如果你直接用 cin是没有这个烦恼的因为 cin 会自动跳过空白字符。我的建议是入门阶段不要在这类题上纠结输入格式直接用 cin 就好。把精力留给核心算法。4.4 递归 find 在更大数据下的隐患这道题 n 只有 1000递归 find 完全可行。但如果你把这份代码模板直接套到更大数据范围的题目上递归深度可能会成为一个隐患。比如遇到一条超长链式的数据递归 find 会导致函数调用栈过深极端情况下会栈溢出。我平时写并查集更喜欢用迭代加路径压缩也就是第 3 节中的写法。这样既不担心递归栈深度也能保证查询时几乎达到常数级别的均摊复杂度。对于 P1892 这道题用递归写法也完全能过但我还是建议尽早养成写迭代 find 的习惯。5. 反集之外这类题还能怎么考5.1 反集是种类并查集的两类特例如果把每个人分成朋友和敌人两类这就是反集。如果把关系扩成 A、B、C 三种互相克制的关系那就需要种类并查集或者带权并查集。最有名的例子是食物链POJ 1182A 吃 BB 吃 CC 吃 A。三倍空间或者维护每个节点到根节点的距离都能解决。你可以把这道题理解成三类之间的循环克制关系而团伙这道题则是两类之间的互斥关系。因此吃透 P1892再去看食物链思路会顺很多。反集其实就是种类并查集里只有同类、异类两种情况时的简化实现。5.2 经典变式题目如果你想趁热打铁我推荐几道和反集密切相关的题关押罪犯NOIP2010把罪犯分到两个监狱要求最小化最大仇恨值。离线按仇恨排序后用反集维护必须分开关的关系思路和这道团伙非常像。食物链POJ 1182三倍并查集的经典题帮助你理解反集从两类扩展到三类时的思路上涨。洛谷的并查集题单里还有很多练习题刷完 P1892 之后可以按难度梯度往上走。这些题本质上都在做同一件事把题面中的关系拆分成同类合并和异类互斥再用反集或带权并查集建模。5.3 给新手的学习建议我的建议是遇到这种关系类题目先别急着敲代码。拿纸笔画一张图左边画 1 到 n 的本体节点右边画 n1 到 2n 的补集节点。敌人关系就画一条从左边本体节点连到右边补集节点的线。手动模拟一组小数据之后再去写代码会清晰得多。写完代码之后一定要把样例跟着程序走一遍不要只看输出对不对。把每次 merge 后的 fa 数组打出来观察根节点的变化。这一步确实有点枯燥但能把并查集的路径压缩、根节点漂移这些细节看得明明白白对后面刷更难的数据结构题帮助很大。最后再分享一个小技巧遇到这种一眼像是并查集、但又多了点弯弯绕的题先想清楚关系是否能传递。能传递的关系走普通并查集互斥的关系就考虑反集多种关系之间互相克制就考虑带权并查集。这套判断逻辑比背代码模板重要得多。