信息学奥赛算法清单里并查集永远是那个“会了就很简单不会就完全没思路”的存在。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] 之后剩余节点就是 [k1, N]剩余图里任意连通块 size 必须满足size N / 2不满足就意味着还得继续打击。1.2 为什么打击对象一定是前缀这题最关键的一个隐含条件就是打击顺序按编号从小到大。很多初学者没注意到这一点以为可以随便挑几个团伙打击那就把题目想难了。如果允许任意删除 k 个点那得二分答案配合并查集反复验证复杂度会上一层楼但本题因为必须从 1 号开始顺次扫所以打击集合天然是前缀 [1, k]剩余集合天然是后缀 [k1, 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))N1000 时上百万级别勉强能跑N1e5 时直接爆炸。更麻烦的是每轮 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(ans1) 对应“打击前 ans 个后”的剩余图因为它包含点 [ans1, N]既然是答案那么 f(ans1) 一定不超过 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 的邻接表里有 jj 的邻接表里也有 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; vectorint 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] isz[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。倒序模拟i3 时没有 v3sz1 合法i2 时发现 v3合并 2 和 3新块大小 2超过 1输出 2。正确。第二组N 4边是星形2-1、3-1、4-1。N / 2 2。只要打掉 1 号剩下的 2、3、4 互不相连每个块大小 1合法所以答案 1。倒序模拟i4、i3、i2 的时候它们的邻居只有 1而 1 还没复活不需要处理每个块大小都是 1i1 时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 错误症状速查表症状可能原因解决办法一直输出 0判断条件写成sz n / 2把合法边界也算成非法或倒序被写成正序改成sz * 2 n检查循环方向答案明显偏大正向模拟删除没有做倒序换倒序加边思路答案明显偏小合并时把v i的边也处理了提前污染图状态只处理v i的边段错误v读到 0 或超范围检查输入格式邻接表只读入 1..N大样例超时每次加入 i 后全图扫所有点求最大块只检查find(i)的 sz递归爆栈极端情况下树高较高按大小合并或把 find 写成循环5.2 关于 N / 2 整除的纠结C 里整数除法是向下取整。N 5 时N / 2 2size 为 2 是合法的size 为 3 就非法。此时判断sz n / 2是正确的。但很多新手写if (sz n / 2)就会把 2 也判成非法导致答案偏大。我习惯写成sz * 2 n因为“超过一半”的直接语义就是两倍大于总数完全避开整除和取整的讨论。N 5size 3 时 6 5 非法size 2 时 4 5 不成立合法。这个写法在奇数、偶数下一律成立强烈推荐。5.3 调试时把倒序过程打印出来我自己刷题时有个土办法在倒序循环里加一行调试输出把每一步的 i、当前 i 所在块大小打出来。比如cerr i i sz sz[find(i)] \n;这样能直观看到 size 从小变大的过程找到第一次超过阈值的位置。当你输出的答案和样例差一点的时候这行日志比任何板子都好使。提交前记得删掉。5.4 一个隐蔽的重复合并问题无向图的边通常会被存两次i 的邻接表里有 jj 的邻接表里也有 i。如果合并时不做v i的过滤两条边都会在倒序过程中被处理。第一次合并没问题第二次合并时两个端点已经在同一个集合里if (a ! b)会把它挡掉从正确性上讲问题不大。真正的问题是如果你把v i的边也合了那相当于在 i 还没复活的时候就让它和已经复活的 j 发生了联系。举个例子N4边 2-1倒序到 i2 时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 正是练习这套提问流程最便宜的练习题花一个晚上把它吃透比盲目刷十道模板题都值。