企业官网建设流程全解析

信息学奥赛算法清单里，并查集永远是那个“会了就很简单，不会就完全没思路”的存在。P1386这道打击犯罪（black），在信息学奥赛一本通提高篇里非常经典：它拿“打击集团”当幌子，考的其实是删除点的维护难题。我当年刷题时正着想了半宿，暴力重建图的代码写了一屏还没过，最后看到题解里那句“倒着加边”才恍然：原来是这么回事。这篇就把这道题从建模到AC完整拆开，重点讲清楚为什么非要用逆向并查集、合并时为什么要加j > i这个条件、以及最容易写错的两个判断点。适合学完并查集模板、想把思路往上拔一截的选手；如果你还不会并查集，先把洛谷 P3367 这种模板题打扎实再看。

另外说明一下，这道题的名字虽然叫“打击犯罪”，但核心根本不在“犯罪”，而在图论模型：有 N 个节点，节点之间有边，现在要按编号顺序删掉前面若干个节点，使得剩下的图里每个连通块都不超过总节点数的一半。这类“删点维持连通性”的题，正着做往往无解，倒过来做却是一道再标准不过的并查集题。

1. 题目到底在说什么

1.1 把故事翻译成图论模型

原题面的背景不用太当真，真正要处理的问题是：有 N 个犯罪集团，编号 1 到 N，集团之间存在若干联系边。警察从编号 1 号开始，按顺序打击集团，也可以理解为必须打击最前面的连续若干个集团，问最少打击多少个，才能让剩下的集团中，任意一个集团直接或间接关联的集团数不超过总数的一半。

翻译成图论语言就是：给定一张 N 个点的无向图，求最小的 k，使得删掉点 1, 2, ..., k 之后，剩余图里每个连通分量的大小都不超过 N / 2（整除）。这里的 N / 2 是向下取整，后面我会专门讲这个坑。

这个模型一旦建立起来，思路就清晰多了。暴力做法当然是枚举 k，每删一批点就重新算一遍连通块大小，但这样复杂度完全扛不住。所以第一步要做的是把“打击”这个动作数学化：打击前缀 [1, k] 之后，剩余节点就是 [k+1, N]，剩余图里任意连通块 size 必须满足size <= N / 2，不满足就意味着还得继续打击。

1.2 为什么打击对象一定是前缀

这题最关键的一个隐含条件，就是打击顺序按编号从小到大。很多初学者没注意到这一点，以为可以随便挑几个团伙打击，那就把题目想难了。如果允许任意删除 k 个点，那得二分答案配合并查集反复验证，复杂度会上一层楼；但本题因为必须从 1 号开始顺次扫，所以打击集合天然是前缀 [1, k]，剩余集合天然是后缀 [k+1, N]。

这个前缀性质是整个逆向算法的地基。它保证了“剩余集团”永远是编号较大的连续一截，于是倒过来恢复时，从 N 号开始往前加，每一步加进来的也都是一个连续后缀，图中的点集合始终是 i..N。要是没有这个性质，倒序加边的做法就不能直接套用。

1.3 先给结论：答案可能为 0

有一种边界是根本不用打击：原始的整张图里，最大连通块大小本来就不超过 N / 2。那答案就是 0。在后面的倒序算法里，这种情况会自然表现为循环跑完都没有触发“非法”条件，最后输出 0。

还有一种是全图都打光的极端情况，一般不讨论，因为打击完 0 个剩余集团，条件自然空洞满足；但按代码逻辑，N 很小的时候可能会直接输出 N。考试不会在这种边界上为难你，理解逻辑即可。

2. 先看暴力，再把并查集拉出来

2.1 正向做法为什么让人头大

如果不假思索地正向模拟，最直接的做法是：枚举 k 从 0 到 N，每次把 1..k 这些点删掉，然后对剩余图跑一次并查集或 DFS，统计每个连通块大小，看满不满足条件。复杂度是 O(N * (N + M))，N=1000 时上百万级别勉强能跑，N=1e5 时直接爆炸。

更麻烦的是，每轮 k 都在变化，连通块随着删除不断分裂，没法复用上一轮的并查集结果。你想用并查集逐步删点？并查集天生不支持拆开已经合并的集合。所以正向思路走到死胡同里，本质原因是“删除”这个操作对并查集不友好。

这时候就该问问自己：如果删除不好做，能不能把删除变成添加？答案是肯定的，这就是后面要讲的倒序。

2.2 并查集需要掌握的三板斧

在进入正题前，把并查集的基础过一遍，因为后面代码全靠它。

第一板斧是路径压缩。查找的时候顺手把路径上的点直接挂到根上，后续查询基本是 O(1) 级别：

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

第二板斧是按大小合并。合并两个集合时，把 size 小的根接在 size 大的根下面，可以防止树退化成链。虽然路径压缩已经很强了，两个一起用更稳。

第三板斧是维护 size。在合并时同步更新根节点的 size，这是本题判断连通块大小是否超标的直接依据。注意 size 只需要存在根节点上，普通子节点不用维护。

2.3 一句话总结并查集的定位

并查集擅长维护“动态加边”下的连通块信息：加一条边，合并两个集合，同时维护每个集合的大小。它不支持“删边”和“拆集合”。所以凡是遇到题目要删除点、删除边、删除区间的连通性，第一反应都该是倒过来做，把删除变成添加。这个思维定势，越早建立越好。

3. 正难则反：把打击倒放成恢复

3.1 倒放录像带的类比

想象一段剪辑好的录像：警察一个一个打掉犯罪集团，画面里团伙的势力范围不断被切断。这段录像正常播放很难分析，因为每分钟都要处理分裂。但如果把录像倒过来放：画面从空荡荡开始，集团一个一个“复活”，边一条一条接上，势力范围不断合并变大。这个倒放过程，每一步都符合并查集的合并逻辑，处理起来毫无压力。

生活里的类比也一样：完整的拼图想小心拆下一块很难，但把一堆碎片按原路拼回去很容易。竞赛算法里的“倒推”“离线”“倒序处理”，很多都是这种思路。

3.2 严格证明：第一次非法时，那个编号就是答案

设答案是 ans，也就是打击前 ans 个集团后合法，打击前 ans-1 个集团后不合法。我们倒着做：从空图开始，依次加入 N, N-1, ..., 1。

记加入 N 到 i 之后，也就是当前图包含点集 [i, N]，图中最大连通块大小为 f(i)。那么：

• f(ans+1) 对应“打击前 ans 个后”的剩余图，因为它包含点 [ans+1, N]，既然是答案，那么 f(ans+1) 一定不超过 N / 2。
• f(ans) 对应“打击前 ans-1 个后”的剩余图，包含点 [ans, N]，如果它合法，说明前 ans-1 个其实就够了，这与 ans 是最小值矛盾，所以 f(ans) 一定超过 N / 2。

所以在倒序过程中，从 N 开始往小加，f(N), f(N-1), ... 一开始都合法，直到加到 ans 的时候第一次出现非法，而这个非法点的编号正好就是答案。反过来写进代码就是：当加入 i 后size > n / 2，直接输出 i 并结束；如果所有 i 加完都没出现非法，输出 0。

这个证明是整道题的灵魂。理解了它，代码基本就是默写。

3.3 为什么只检查 i 所在的连通块就够了

初学者最容易担心一个问题：倒序加入点 i 时，会不会别的地方某个连通块早就偷偷超过限制了？

不会。因为每次加入 i，只可能让 i 所在的连通块变大，其他连通块根本没有机会发生变化。而那些没变化的连通块，在它们被加入的时候都已经检查过一遍，当时是合法的，之后又没被碰过，现在自然依然合法。

所以每加入一个 i，只需要检查find(i)这个根下面的 size 即可，不需要全图每个块都扫一遍。这个优化很多人知道，但很少有人想明白为什么对。写代码时这句话直接体现在判断条件上：

if (sz[find(i)] > n / 2) { ... }

3.4 合并边时为什么要加j > i

这是最容易写错的一个细节。倒序做到 i 时，编号大于 i 的点已经全部“复活”，编号小于 i 的点还没出现。i 的邻居列表里可能既有大于 i 的，也有小于 i 的，但我们只能跟“当前已经存在的点”合并，所以只处理j > i的邻居。

同时，题目给的是无向边，通常 i 的邻接表里有 j，j 的邻接表里也有 i。如果两条边都处理，就会重复合并，虽然并查集合并不报错，但如果你把j < i也合并了，等于把还没复活的点提前拉进图里，判断时机就完全错乱了。

正确的理解是：每条无向边 (u, v)，设 u < v，那么它一定是在倒序处理到 u 的时候，通过 u 的邻接表里找到 v 并合并的。处理 v 的时候，虽然它的邻接表里也有 u，但因为 v 的编号更大，处理到 v 时 u 还没复活，所以不会误合。这样就保证了每条边恰好在一个正确的时机被处理。

4. 完整代码与逐段拆解

4.1 可直接提交的 C++ 代码

代码不长，核心不超过 40 行：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; vector<int> e[MAXN]; int fa[MAXN], sz[MAXN]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { int m; cin >> m; while (m--) { int v; cin >> v; if (v != i) e[i].push_back(v); // 自环可以忽略 } } for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; } for (int i = n; i >= 1; i--) { for (int v : e[i]) { if (v > i) { int a = find(i), b = find(v); if (a != b) { if (sz[a] < sz[b]) swap(a, b); fa[b] = a; sz[a] += sz[b]; } } } if (sz[find(i)] * 2 > n) { cout << i << '\n'; return 0; } } cout << 0 << '\n'; return 0; }

这里判断条件写成了sz * 2 > n，它等价于sz > n / 2，但语义上更符合“超过一半”的表述，也规避了整除带来的纠结，后面会细说。

4.2 逐段解释关键逻辑

读入部分：对每个 i，先读一个 m，表示 i 和多少个集团有联系，再读 m 个邻居编号。把每个邻居塞进邻接表。自环对连通性没有影响，直接跳过。

初始化部分：每个人都单独成一个集团，fa[i] = i，sz[i] = 1。

倒序部分：i 从 n 递减到 1。遍历 e[i] 中所有邻居 v，只处理 v > i 的边。合并前先 find 两端，如果不在同一个集合，按大小合并，并更新大根的 sz。每次加完 i 的所有合法边后，立刻检查 i 所在连通块是否超过上限，超了就输出 i 并结束。

注意检查时机必须在合并完所有边之后，不能放在合并循环里。因为可能单条边没超，全部合完才超；也可能合完也没超。如果放在中间检查，会漏掉后几条边造成的增量。

4.3 用两组自测数据验证答案

第一组：N = 3，边是 1-2、2-3，也就是三个点连成一条链。N / 2 = 1，意味着任何连通块最多只能有 1 个人，所以必须把前 2 个都打掉，答案应该是 2。

倒序模拟：i=3 时没有 v>3，sz=1 合法；i=2 时发现 v=3，合并 2 和 3，新块大小 2，超过 1，输出 2。正确。

第二组：N = 4，边是星形：2-1、3-1、4-1。N / 2 = 2。只要打掉 1 号，剩下的 2、3、4 互不相连，每个块大小 1，合法，所以答案 1。

倒序模拟：i=4、i=3、i=2 的时候，它们的邻居只有 1，而 1 还没复活，不需要处理，每个块大小都是 1；i=1 时，1 的邻居 2、3、4 全部复活，一口气合并成一个大小 4 的块，4 * 2 > 4，输出 1。正确。

这两组数据一大一小，正好覆盖了“加边后合法”和“加边后非法”两种情况，自己写完代码后建议手测一遍。

4.4 几个可选的优化方向

一是快读。本题 N 范围不大，ios::sync_with_stdio(false)足够了，没必要写 getchar 快读。如果将来遇到 N 到 1e5、边到 1e6 的加强版，快读和链式前向星才是更好的选择。

二是邻接表去重。输入可能有重复边，但对并查集来说重复合并是幂等操作，不影响正确性，所以去重只是省一点时间。自环会被v > i的条件天然过滤掉，不用担心。

三是在合并方向上的选择。我按 size 合并，确保树高可控。有的写法直接写fa[a] = b，在本题数据弱时也能过，但养成了坏习惯，遇到大数据容易退化。

5. 常见问题排查与避坑实录

5.1 错误症状速查表

5.2 关于 N / 2 整除的纠结

C++ 里整数除法是向下取整。N = 5 时，N / 2 = 2，size 为 2 是合法的，size 为 3 就非法。此时判断sz > n / 2是正确的。但很多新手写if (sz >= n / 2)就会把 2 也判成非法，导致答案偏大。

我习惯写成sz * 2 > n，因为“超过一半”的直接语义就是两倍大于总数，完全避开整除和取整的讨论。N = 5，size = 3 时 6 > 5 非法；size = 2 时 4 > 5 不成立，合法。这个写法在奇数、偶数下一律成立，强烈推荐。

5.3 调试时把倒序过程打印出来

我自己刷题时有个土办法：在倒序循环里加一行调试输出，把每一步的 i、当前 i 所在块大小打出来。比如：

cerr << "i=" << i << " sz=" << sz[find(i)] << '\n';

这样能直观看到 size 从小变大的过程，找到第一次超过阈值的位置。当你输出的答案和样例差一点的时候，这行日志比任何板子都好使。提交前记得删掉。

5.4 一个隐蔽的重复合并问题

无向图的边通常会被存两次：i 的邻接表里有 j，j 的邻接表里也有 i。如果合并时不做v > i的过滤，两条边都会在倒序过程中被处理。第一次合并没问题，第二次合并时两个端点已经在同一个集合里，if (a != b)会把它挡掉，从正确性上讲问题不大。

真正的问题是如果你把v < i的边也合了，那相当于在 i 还没复活的时候，就让它和已经复活的 j 发生了联系。举个例子：N=4，边 2-1，倒序到 i=2 时，1 还没复活，如果错误地合并 2 和 1，最终结果就会把 1 的“复活”提前到 2 这一步，判断全乱。所以筛边条件必须写死v > i，不能写成v != i或者不筛。

6. 题后思考与同类题迁移

6.1 倒序加边全家桶

P1386 打击犯罪并不是孤例。图论里有一类题全部是“正序删除、倒序添加”的套路。

比如经典的洛谷 P1197 星球大战，题目不断摧毁一些星球并询问当前连通块数量，正着做每次都要重算，倒着做就是把被摧毁的星球按逆序加回来，每加一次看合并减少了几块，逆序输出答案就行。

再比如 USACO 的 Closing the Farm，农场关闭，每次关一个农场后要判断剩余农场是否全部连通，倒序开启农场、加边并查集，几乎就是一个模子刻出来的。

认准这个模式：看到“删点后询问连通块性质”，先别急着写，想一想能否倒过来。

6.2 带权并查集和离线思想

这道题能顺利解决，很大程度上因为打击顺序固定。如果哪天遇到“任意删除 k 个点”变体，那就需要二分答案，每轮用并查集验证 mid 可行不可行，复杂度变成 O(N log N) 级别，但核心依然是并查集维护连通块大小。

再往后学，并查集还有很多进阶用法：洛谷 P2024 食物链是带权并查集，维护节点到根的种类关系；银河英雄传说维护距离；NOI2015 程序自动机分析是并查集加离散化离线处理约束矛盾。这些题本质都在控“集合与集合之间的关系”，只是信息量从“是否连通”升级成了“距离多远、种类是否相同”。

6.3 正难则反这个思维到底值多少分

一道题如果正着做要删点删边，复杂度下不来，往往倒过来想就是柳暗花明。这种思维不是天上掉下来的，而是靠刷类似题堆出来的。P1386 好在哪儿？好就好在它把“倒序添加”这个思想放在一个最小规模的题目里，让你花半小时就能彻底吃透，之后遇到星球大战、关闭农场，你会觉得这就是老朋友。

我自己现在的习惯是：遇到任何“删除 + 查询静态属性”的题，先停十秒，问自己三个问题——删除顺序是什么？倒过来是不是变量添加？添加后的属性能不能拿并查集、树状数组这种经典结构维护？三问之后，大概率能确定方向再动手。P1386 正是练习这套提问流程最便宜的练习题，花一个晚上把它吃透，比盲目刷十道模板题都值。