刷题刷到信息学奥赛一本通 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 不超过 1000，m 不超过 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 是每个人的"本体"，n+1 到 2n 是每个人的"敌人集合代表"。
更准确地说，对于人 i，i 所在的集合表示"i 的朋友集合"，i+n 所在的集合表示"i 的所有敌人"的集合。注意，i+n 不是一个真人，而是一个虚拟节点，它专门用来收集"哪些人和 i 有仇"。
当题目告诉你 a 和 b 是敌人时，我们做两件事：
- 把 b 并到 a 的敌人集合里：merge(b, a+n)
- 把 a 并到 b 的敌人集合里：merge(a, b+n)
这样设计之后，任意两个人都可以通过各自的敌人阵营产生间接联系。同时，敌人关系本身并没有让 a 和 b 出现在同一个朋友集合里，a 和 b 依然不是朋友，符合题意。
这个方法在很多资料里叫"反集"或"补集"。它的思想本质上是用空间换逻辑：多开一倍空间，给每个人安排一个"影子位置"，专门收纳敌人。
2.3 为什么两条 merge 能实现"敌人的敌人是朋友"
假设有三个人 a、b、c，已知 a 和 b 是敌人，a 和 c 也是敌人。
按上面的规则，处理"a 和 b 是敌人"时，执行 merge(b, a+n) 和 merge(a, b+n)。其中 merge(b, a+n) 这一步，把 b 放进了 a 的敌人阵营。
处理"a 和 c 是敌人"时，同样执行 merge(c, a+n) 和 merge(a, c+n)。此时 c 也进入了 a 的敌人阵营。
现在 b 和 c 都在 a+n 这个集合里，所以 b 和 c 自动成为同一个朋友集合里的人。全程没有任何一步在主动 merge(b, c)，但通过共同的 a+n，b 和 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 我特意写成了"小号优先"。为什么？因为补集节点的编号在 n+1 到 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 对根去重：
set<int> st; for (int i = 1; i <= n; i++) { st.insert(find(i)); } cout << st.size() << endl;为什么会有这种差异？因为在并查集合并过程中，根节点有可能会漂移到 n+1 到 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 到 6：
- 1 的根是 1
- 2 的根是 2
- 3 的根是 3
- 4 的根是 2
- 5 的根是 3
- 6 的根是 2
find(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 1182）：A 吃 B，B 吃 C，C 吃 A。三倍空间或者维护每个节点到根节点的距离，都能解决。你可以把这道题理解成"三类之间的循环克制关系"，而团伙这道题则是"两类之间的互斥关系"。
因此，吃透 P1892，再去看食物链，思路会顺很多。反集其实就是种类并查集里只有"同类、异类"两种情况时的简化实现。
5.2 经典变式题目
如果你想趁热打铁，我推荐几道和反集密切相关的题：
- 关押罪犯（NOIP2010）：把罪犯分到两个监狱，要求最小化最大仇恨值。离线按仇恨排序后，用反集维护"必须分开关"的关系，思路和这道团伙非常像。
- 食物链（POJ 1182）：三倍并查集的经典题，帮助你理解反集从两类扩展到三类时的思路上涨。
- 洛谷的并查集题单里还有很多练习题，刷完 P1892 之后可以按难度梯度往上走。
这些题本质上都在做同一件事：把题面中的关系拆分成"同类合并"和"异类互斥"，再用反集或带权并查集建模。
5.3 给新手的学习建议
我的建议是，遇到这种关系类题目，先别急着敲代码。拿纸笔画一张图：左边画 1 到 n 的本体节点，右边画 n+1 到 2n 的补集节点。敌人关系就画一条从左边本体节点连到右边补集节点的线。手动模拟一组小数据之后，再去写代码会清晰得多。
写完代码之后，一定要把样例跟着程序走一遍，不要只看输出对不对。把每次 merge 后的 fa 数组打出来，观察根节点的变化。这一步确实有点枯燥，但能把并查集的路径压缩、根节点漂移这些细节看得明明白白，对后面刷更难的数据结构题帮助很大。
最后再分享一个小技巧：遇到这种一眼像是并查集、但又多了点弯弯绕的题，先想清楚"关系是否能传递"。能传递的关系走普通并查集，互斥的关系就考虑反集，多种关系之间互相克制就考虑带权并查集。这套判断逻辑比背代码模板重要得多。
