企业官网建设流程全解析

第一次做完 P1892 这道“团伙”题，我的第一反应不是“原来并查集还能这么用”，而是“幸好没在笔试现场遇到它”。题面看着像模拟题：一群人，一些是朋友，一些是敌人，朋友的朋友还是朋友，敌人的敌人也是朋友——听上去得靠 BFS 维护关系网络。可实际上，它是并查集的经典扩展题，考察的是你愿不愿意把一个“人”拆成两个节点来建模。这篇文章会从题意翻译开始，一路讲到扩展域代码的每一行、我踩过的三个坑，以及这套思路在后来的同类题目里怎么迁移。如果你已经会写路径压缩，但遇到这类“有对立关系”的题目总想用图论去碰，那这篇正好适合你。

1. 题面里的两句话，怎么翻译成数据结构

1.1 两种关系，一张人脉网

题目描述的是 n 个人之间的两种二元关系：朋友（F）和敌人（E）。朋友关系比较好理解，两个人是朋友，就属于同一个团伙；敌人关系则复杂一些，它是推导新朋友关系的起点。题目给出一系列“谁和谁是朋友”或“谁和谁是敌人”的信息，最终要回答：这些人一共能分成多少个团伙。

很多人一看到“朋友的朋友是朋友”“敌人的敌人是朋友”，下意识想的是建图然后跑 Tarjan 或 BFS。这个思路不能说错，但没抓住本质。朋友关系确实可以看作连通关系，而敌人关系的作用是“翻转变换”：A 和 B 是敌人，B 和 C 是敌人，那么 A 和 C 就被翻转成朋友关系，从而可能把两个本不相干的团伙合并起来。

举个例子直观感受一下。如果只有三组关系：1 和 2 是敌人，2 和 3 是敌人。按照规则，1 和 3 因为共享敌人 2，所以变成了朋友，那么团伙应该分成 {1, 3} 和 {2} 两个。这里“敌人”不是简单的“不连通”，而是承担了中间人的角色，负责把一对敌人分别拉入对方的“对立面”，再由对立面传导出新的朋友关系。这种“非单纯合并”的关系，正是这道题和普通并查集入门题最大的区别。

1.2 推导规则的本质：在图上找连通块

如果你把朋友关系看成“正向边”，把敌人关系看成“反向边”，那题目实际上是在问：经过若干次取反操作后，哪些点最终连通在一起。普通并查集能维护正向连通，但维护不了“取反”这个动作，因为你没有一个地方能记录“这个点和那个点是敌人”这一事实。

所以解题的关键，不是用什么高级图论算法，而是给每个“人”分配额外的身份节点，让“敌人关系”也能变成一种可以被合并的连通关系。就像一张人脉网，不仅有“好友分组”，还有“黑名单分组”。敌人关系就是双方各自进入对方黑名单分组的操作，而所有黑名单分组的传递又会反过来影响好友分组。一旦想通这一点，剩下的就是并查集模板的事了。

2. 为什么普通并查集撑不起“敌人的敌人是朋友”

2.1 普通并查集只能表达“同类归堆”

先回顾一下普通并查集解决什么问题：给定若干个点，每次告诉你两个点属于同一个集合，最后问有多少个互不相交的集合。它把所有信息都合并成“平等、同类”的关系。如果题目只有朋友关系，那确实只需要一个 n 节点的并查集，F a b 就是 unite(a, b)，最后数根就行。

但敌人关系不能这么处理。如果 A 和 B 是敌人，你不能直接 unite(A, B)，因为那样等于把敌人当朋友处理；你也不能什么都不做，因为那样“A 和 B 是敌人”这个信息就丢失了。等后面出现“B 和 C 是敌人”时，你想利用“敌人的敌人是朋友”这条规则把 A 和 C 拉进同一个团伙，会发现没有任何结构记录了 A 和 B 曾对立过。

一个很自然的想法是开一个 enemy 数组，记录每个人的敌人有哪些，再用这个信息去触发合并。但在链式关系较长时，这种“外部标记”很容易漏：谁是谁的敌人、谁是谁的敌人的敌人，层层嵌套，代码会越写越乱，最终不可维护。

2.2 一个反例：敌人关系没法直接往里塞

我们看一组只有三个人的输入：1 E 2，2 E 3。正确结果是两个团伙：{1, 3} 和 {2}。如果用普通并查集，只对朋友关系做合并，敌人关系一律忽略，那么 1、2、3 三个点之间没有任何合并操作，最后会得到三个团伙。这显然是错的，因为我们丢失了“1 和 2 敌对”这个事实，也就无法推导出“1 和 3 因为共同敌人 2 而成为朋友”。

换一种做法：把敌人关系也合并，比如遇到 E 就 unite(a, b)，那结果更离谱——1、2、3 全成一个集合，等于把敌对关系全当成友好关系处理。这说明，敌人的信息不能简单“塞进”原来的点里，必须有一个独立的维度去承载它。

2.3 拆点：把“身份”拆成阵营节点

扩展域的核心思路是：对每个原始编号 i，创建两个节点，i 和 i + n。其中 i 表示“i 作为朋友的身份”，i + n 表示“i 作为敌人的身份”。这两个身份节点在同一个并查集结构里，但可以自由连通。

• 如果 a 和 b 是朋友，就让 a 的朋友身份和 b 的朋友身份合并；同时，a 的敌人身份和 b 的敌人身份也应该合并。因为朋友共享同一个“朋友圈”，也共享同一批“敌人圈”。
• 如果 a 和 b 是敌人，就做交叉合并：a 的朋友身份连到 b 的敌人身份，b 的朋友身份连到 a 的敌人身份。

这样一来，“敌人的敌人是朋友”不再需要手动推导，而是由并查集的传递性自动完成：a 和 b 敌对，b 和 c 敌对，那么 a 的朋友身份会通过 b 的敌人身份连到 c 的朋友身份，合并过程自动让 a 和 c 站到同一个集合里。

3. 扩展域完整代码：每行都在干什么

3.1 数组初始化与查找合并模板

下面是完整的 C++ 实现，为了方便讲解，我这里用了非递归的 find，避免递归深度带来的无谓风险。

#include <bits/stdc++.h> using namespace std; vector<int> fa; 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 unite(int x, int y) { x = find(x); y = find(y); if (x != y) fa[x] = y; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; fa.resize(2 * n + 5); for (int i = 1; i <= 2 * n; ++i) fa[i] = i; char op; int a, b; while (m--) { cin >> op >> a >> b; if (op == 'F') { unite(a, b); unite(a + n, b + n); } else { unite(a, b + n); unite(b, a + n); } } vector<int> vis(2 * n + 5, 0); int ans = 0; for (int i = 1; i <= n; ++i) { int r = find(i); if (!vis[r]) { vis[r] = 1; ++ans; } } cout << ans << '\n'; return 0; }

数组开 2n + 5 是因为我们要用到编号 1 到 2n，多开几个是防止越界时还得回头改代码。并查集初始化从 1 开始，到 2n 结束，保证每个身份节点最初都是独立的根。find 用两趟循环实现路径压缩，第一趟找根，第二趟把路径上的所有节点直接挂到根上，效果等价于递归写法。

3.2 朋友关系：两个域要一起合并

这里的写法我特意强调一下：处理朋友关系时，除了 unite(a, b)，还要 unite(a + n, b + n)。很多精简题解只写了前者，在小数据上也能过，但那是数据不够强，不代表逻辑完整。

原因是这样的：a 和 b 是朋友，意味着 a 的好友也是 b 的好友；反过来，a 的敌人同样也是 b 的敌人。如果你只合并了“朋友身份”，没有合并“敌人身份”，那么当后续出现一条长链时，敌方关系就断掉了。我举个六人链的例子：1 F 2，2 E 3，3 F 4，4 E 5，5 F 6。

按照完整写法推导，最终团伙是 {1, 2, 5, 6} 和 {3, 4} 两组。因为 1 通过 2 与 3 敌对，3 又和 4 是朋友，所以 4 和 1 也是敌对关系；而 4 和 5 敌对，所以 5 又通过 4 和 1 变成了朋友。如果朋友关系只合并了朋友域，这条“敌对→敌对”的传导就会在中途断裂，最终会错误地分出三组甚至更多组。合并敌人域之后，整个推导链才完整。

3.3 敌人关系：交叉合并两个方向

敌人关系的两行代码是核心中的核心：

unite(a, b + n); unite(b, a + n);

第一行表示“a 是 b 的敌人”，第二行表示“b 也是 a 的敌人”。两个方向缺一不可，因为敌人关系是对称的，不是单向的。假设只写 unite(a, b + n)，那么 a 识别了 b 是敌人，但 b 那边并不知道 a 是敌人。等后面某个推导需要用到“b 的敌人是 a”这个事实时，并查集里根本找不到这条边，结果就会错。

我自己曾经在这上面翻过车：只写了一行，样例过了，交上去挂了好几个点。后来打印出所有合并后的根节点，才发现方向不对称导致大量本应同组的点被拆开了。所以看到敌人的输入，请条件反射式地把两行交叉合并都写上，不要偷懒。

3.4 答案统计：对前 n 个节点的根去重

最后统计团伙数时，只需要看原始编号 1 到 n 这些“朋友身份”节点各自属于哪棵树。因为 1 到 n 节点才是真正参与团伙归属的实体，n + 1 到 2n 节点只是辅助推导用的“敌人身份”，不应该被单独算成一个团伙。

统计方法有很多，最稳的是拿一个 vis 数组标记前 n 个节点的根：

vector<int> vis(2 * n + 5, 0); int ans = 0; for (int i = 1; i <= n; ++i) { int r = find(i); if (!vis[r]) { vis[r] = 1; ++ans; } }

这里 vis 的下标是根节点的编号，可能是 1 到 2n 之间的任意值，所以 vis 数组也要开到 2n 级别，否则很容易越界。

4. 实测踩坑：合并方向、读入与统计陷阱

4.1 只写单向合并造成的关系不对称

这个坑在 3.3 节已经提了一嘴，但实际出错的隐蔽性比想象中高。你可能会想：a 是 b 的敌人，那我不就是 unite(a, b + n) 吗？为什么还要写 unite(b, a + n)？

原因很简单：并查集是无向的连通结构，但它不会自动把“a 敌视 b”变成“b 敌视 a”。如果不显式写第二行，那 b 的朋友身份永远不知道 a 的敌人身份存在。后面如果出现“b 的朋友 c 需要推导和 a 的关系”，这层关系就接不上。排查方法也很直接：每次处理完敌人关系，自己动手查一下 find(a) 和 find(b + n)、find(b) 和 find(a + n) 是否分别同根。两组都同根才说明双向关系建立成功。

4.2 朋友关系漏合并敌人域，链式推导会断

这是这道题对于我来说最隐蔽的坑，比单向敌人关系还难发现。样例通常很短，怎么合并都能过；但一旦关系链变长，比如朋友和敌人交替出现，漏掉朋友关系的敌人域合并，答案就会偏大。

我在 3.2 节给的六人链，就是你本地对拍时最值得先测的数据。如果按“只合并朋友域”的弱实现走，输出会是 3；按完整实现走，输出是 2。你可以在自己的代码里加两行测试用打印，把每次 unite 之后前 n 个节点的根数组打出来，一眼就能看出哪些该连的没连上。

另外说明一下，这个“多合并”会不会把本来不该合并的组合并掉？在数据自洽的前提下不会。因为敌人的敌人是朋友这个规则本身就是一个闭包运算，扩展域合并操作只是把这个闭包显式地建立起来。真正因为弱实现导致的关系缺失，才是更常见的错误来源。

4.3 输入字符、数组大小与递归栈

读入时有一个细节：操作符是一个字符，后面跟着两个整数。用 cin >> op 是最省心的，它会自动跳过空白符，无论是空格还是换行都不影响。如果用 scanf，格式串里记得在 %c 前加一个空格，写成 " %c%d%d"，否则容易把残留的换行符读进去。

数组大小建议直接写成 2 * n + 5，不要写 2 * n。因为敌人域的下标最坏会到 2n，如果只开 2n，下标 2n 本身还能用，但多开几个能防止不小心把下标算到 2n + 1 时直接越界。递归 find 在数据规模小的时候没问题，但有些评测环境栈比较浅，或者以后遇到更大的 n，建议直接使用本文给出的非递归两趟写法，一劳永逸。

4.4 统计时不能用 find(i) == i

最后统计答案时，有一个看起来理所当然、实则大错特错的写法：

int ans = 0; for (int i = 1; i <= n; ++i) if (find(i) == i) ++ans;

为什么错？因为合并方向不一定是“小号合并到大号”。比如只有两个点，输入 1 E 2，扩展域合并后可能变成 1 连到 3、2 连到 4。此时 find(1) 是 3，find(2) 是 4，都不等于自身，按上面的写法答案就是 0，但实际团伙数应该是 2。这个坑不踩一次，真不知道并查集的根也可以跑到后半区。

所以统计团伙数，要么用 vis 数组标记前 n 个节点的根，要么直接塞进 set 去重。千万别默认根一定在 1 到 n 范围内。

5. 复杂度分析与同类题型延伸

5.1 时空开销到底多大

这道题的数据范围不算大，但分析一下复杂度能帮你建立选型直觉。每次 find 和 unite 在路径压缩下几乎都是常数级别，实际复杂度可以认为近似 O(α(n))，α 是反阿克曼函数，增长极其缓慢。所有操作加起来就是 O(m·α(n))，其中 m 是关系数量。空间上开 2n 个节点，自然是 O(n)。

即使以后遇到 n 达到数十万、关系数达到数十万级别的类似题目，扩展域并查集依然是第一选择。它不像图论算法那样需要建邻接表或跑多轮遍历，代码短、常数小，性能表现非常稳。

5.2 从“两个域”到“k 个域”的种类并查集

扩展域并查集的通用形式是：每个实体开 k 个节点，代表 k 种状态。关系操作就是状态之间的合并。像这道题只有“朋友”和“敌人”两种状态，所以开 2n 个节点；如果遇到更复杂的循环关系，比如“A 吃 B，B 吃 C，C 吃 A”，就可以开 3n 个节点，分别表示“同类”“捕食者”“被捕食者”三种身份，然后按照关系矩阵做交叉合并。

这种“拆点建图”的思路，本质上是在并查集里显式表达二元或多元关系，而不是像朴素并查集那样只表达“是否同类”。碰到“颜色交替”“阵营对立”“食物链上下级”这类题，优先想一想能不能拆成两类或多类节点，很多时候比硬上图论算法简单得多。

5.3 什么时候该用带权并查集

扩展域虽然直观，但状态一多，节点数量会线性膨胀。比如每个实体有 10 种状态，就要开 10n 个节点，不管是空间还是合并逻辑都会变得笨重。这时候可以考虑带权并查集：在每条边或每个节点上维护一个权值，表示它和根节点的相对关系，通过权值运算实现关系的传递和变换。

带权并查集的经典应用是“三点循环关系”一类的题目。它的优点是空间还是 O(n)，缺点是写起来更绕，合并时权值的加减法容易搞混。我的个人建议是：状态数量少、关系是简单的“同类/对立”时，无脑用扩展域；状态数量多、关系有成环的克制链时，再考虑带权并查集，两者各有各的舒适区。

回到 P1892 这道题本身，它最值得记下来的，其实是那个“拆点”的思考方式。我在做后面的食物链、关押罪犯等同类题时，都还在用这套思路打底。如果你想把这题吃透，不妨把本文代码里的 F 分支先改成只合并朋友域的弱实现，再拿 3.2 节那条六人链去对拍，亲眼看到错误结果之后，对“两个域都要合并”这点的理解会深很多。这比自己空想十遍规则都管用。