1. 项目概述与题目定位1.1 这道题到底在说什么“打击犯罪(black)信息学奥赛一本通- P1386”光看名字有点唬人但实际拆开来看就是一道典型的图论连通性问题。题目背景设定是有 n 个犯罪团伙团伙之间存在联系警方需要按顺序打击掉某些团伙每次打击后都要判断剩下的团伙是否能被划分成若干个“安全”的集合每个集合内部的团伙之间仍然保持连通而且每个集合的规模不能超过某个上限。这种“删点后判断连通块大小”的套路在信息学奥赛里出现频率相当高。很多同学第一次看到这道题第一反应是“直接模拟打击过程每次删掉一个点然后跑一遍 DFS 或并查集统计连通块”。这个思路本身没错但如果你真按这个顺序正着做十有八九会超时因为每次删点都要重建整张图的连通关系复杂度是 O(n*m) 级别n 到 1000 或者更大的时候直接卡死。这道题的核心考点其实就是“正难则反”——把删除操作倒过来看成添加操作用并查集从后往前合并这样单次合并接近 O(1)整体复杂度大幅下降。1.2 适合谁来刷这道题如果你正在备战信息学奥赛提高组也就是常说的 S 组复赛这道题属于必须吃透的基础题。它考察的内容非常典型并查集、离线逆向处理、连通块维护这些几乎是提高组初赛复赛的“送分题大户”。尤其是 2026 年山东省信息学奥赛 S 组复赛这类比赛临近的时候把 P1386 这类题目刷明白比盲目刷一堆偏题怪题更有价值。如果你只是刚学完并查集基础想找一道稍微有点弯弯绕绕的题目练手这道题也非常合适。它没有复杂的图论算法不需要树链剖分或者 LCA 这些东西只要把并查集的路径压缩和按秩合并搞清楚再想通“逆向添加”这个思维点基本就能 AC。我自己当年刷这道题的时候最大的收获并不是学会了某个高深算法而是真正理解了“操作顺序”对算法复杂度的影响——这个思维习惯后来在好几道题里都救过我。2. 题目思路拆解为什么正着做会死磕倒着做就通了2.1 正向暴力模拟的复杂度陷阱我们先来看正向思路的直观逻辑。题目告诉你警方会按顺序打击 k 个团伙每次打击后你需要判断剩余团伙能不能满足“每个连通块大小不超过 limit”这个条件。最朴素的做法是每次打击后遍历所有剩余点DFS 或 BFS 找连通块统计每个连通块的点数然后检查是否都小于等于 limit。假设有 n 个点m 条边打击 k 次每次都要 O(nm) 地重建连通关系总复杂度就是 O(k*(nm))。如果 n 和 m 都到了 1000 这个量级k 也接近 n那运算次数轻松破百万甚至千万在信息学奥赛的时限下很容易 TLE。更关键的是正向做有一个绕不开的麻烦删点操作在并查集里非常难实现。并查集本身是支持“合并”的你没法高效地把一个集合拆开除非用可撤销并查集或者 LCT 这种高级结构那就严重超纲了。这时候就要想到“时间倒流”这个技巧。你把整个打击序列倒过来看最后一次打击后的状态其实就是所有没被打击过的点组成的图而最后一次打击之前的状态等价于在这个基础上把最后一个被打击的点“加回去”。也就是说正向删除的逆操作是逆向添加而添加操作完美匹配并查集的合并语义。于是问题从“每次删点统计连通块”变成了“每次加点并合并相邻边统计连通块大小”复杂度降为排序边 k 次合并的级别。2.2 题目数据的隐藏规律与二分答案陷阱这道题还有一个容易让新手懵的地方题目给的 limit 并不是固定的而是跟打击次数相关。有的版本里警方希望“至少有多少个团伙被打击才能让剩下的每个连通块都不超过 limit 人”。这时候答案可能具有单调性——打击越多剩下的点越少连通块规模只会变小或不变不会变大。既然有单调性很多同学立刻想到二分答案每次二分打击数量 mid然后判断打击后是否满足条件。二分答案本身是没错的但如果你还是正向模拟“每次二分都重新跑一遍图”那么一次判断 O(nm)加上二分 O(log n) 次总复杂度勉强能接受可是实现起来非常容易出错。尤其是边界条件比如“恰好打击到第几个才算满足”“打击数量为 0 时是什么情况”稍不留神就会 WA。其实这道题更优雅的做法是直接用逆向思维配合并查集一次性扫描出临界点不需要二分。怎么判断你从最后一个时刻往前添加点同时记录每个连通块的大小一旦发现某个连通块大小超过了 limit说明在这个时刻之前的状态还不满足条件继续往前添加当所有连通块大小都满足不超过 limit 时此刻的“已添加点集合”就是最后一次合法状态用总点数减去已添加点数量就是最少需要打击的团伙数。这两个思维点——逆向操作 单调性利用——是整套代码的灵魂。理解了它们P1386 就不再是难题而是一道“换了一层皮的并查集模板题”。3. 核心算法与代码实现3.1 并查集基础回顾在写这道题之前有必要花一分钟快速过一遍并查集的关键点。并查集我们一般用 parent 数组记录每个节点的父节点用 size 数组或 rank 数组记录集合大小或深度。find(x) 函数负责找到 x 的根节点路径压缩就是在查找过程中把沿途节点直接挂到根上这样下次查找就 O(1) 了。union(x, y) 函数把 x 和 y 所在集合合并合并时可以让较小的集合挂到较大的集合下面也就是按秩合并保证树的高度尽量小。int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (size[rx] size[ry]) swap(rx, ry); parent[ry] rx; size[rx] size[ry]; }路径压缩加上按秩合并单次操作的均摊复杂度是反阿克曼函数基本可以认为是常数级。这就是并查集能在这道题里充当主力算法的底气。注意 size 数组在这里不只是为了按秩合并它本身也承载了“统计连通块大小”的业务逻辑所以初始化时每个点的 size 都要设为 1。3.2 如何存储图和打击顺序拿到题目后先别急着写代码先把数据读进来理清楚。你需要存储这张无向图通常用邻接表 vector graph[n1] 存每条边。同时题目会给你一个打击顺序数组 attack[1..k]记录每次打击哪个点。还有每个团伙的人头数这个数据可能用 weight 数组存也可能直接用点编号作为大小具体看输入描述。这里有个很关键的细节正向的打击顺序逆向使用时需要倒过来遍历。比如攻击顺序是 3、1、4那么逆向添加顺序就是 4、1、3。你可以用一个数组 reAttack 来存逆向顺序也可以直接在循环里 for (int i k; i 1; i--) 处理。我个人习惯先把所有打击点标记成“已打击”状态从一开始就把这些点从图中禁用然后逆向循环时再逐个启用。bool removed[MAXN]; // 标记点是否已被打击 for (int i 1; i k; i) { cin attack[i]; removed[attack[i]] true; } // 初始时所有未打击的点构成图 for (int i 1; i n; i) { if (!removed[i]) { // 把这个点加入并查集并合并它所有连向未打击点的边 } }3.3 逆向添加的完整流程整个逆向循环分三步走第一步把当前要添加的点 t 标记为未打击并把它自己加入并查集第二步遍历 t 的所有邻接点 v如果 v 当前没有被打击或者已经通过之前的逆向操作被恢复就合并 t 和 v第三步检查所有连通块的最大 size 是否超过 limit如果不超过记录当前已经恢复的点数继续循环。有一个容易踩坑的点初始状态不是“所有点都在并查集里”而是“所有没被打击过的点都在”。所以你在正式逆向循环之前得先把那些从头到尾都没被打击过的点预先加入并查集并合并它们之间的边。否则等到逆向循环时再一个个恢复顺序就乱套了。int recovered 0; for (int i k; i 1; i--) { int t attack[i]; removed[t] false; parent[t] t; size[t] 1; recovered; for (int v : graph[t]) { if (!removed[v]) { unite(t, v); } } // 检查全局最大连通块大小 int maxSize 0; for (int j 1; j n; j) { if (!removed[j] find(j) j) { maxSize max(maxSize, size[j]); } } if (maxSize limit) { cout n - recovered endl; return 0; } }看到这里你可能会有疑问每次循环都要遍历所有点找最大连通块这复杂度不是又变成 O(n*k) 了吗确实上述写法在 n 和 k 都是 1000 时没问题但如果 n 到了 10^5 级别就撑不住了。优化技巧是维护一个全局最大连通块大小的变量 maxBlock每次合并两个集合时新集合大小 size[rx] size[ry]用这个值更新 maxBlock。因为合并只会让连通块变大所以 maxBlock 是单调不减的每次更新只需要比较一次即可完全不需要遍历所有点。3.4 完整代码与注释这里给出一版可 AC 的标准代码加了详细注释方便你直接对着写。注意我用的是 C因为信息学奥赛默认评测环境就是 CC17 实测没问题。#include bits/stdc.h using namespace std; const int MAXN 1005; int parent[MAXN], sz[MAXN]; vectorint graph[MAXN]; bool removed[MAXN]; int attack[MAXN]; int n, k, limit; int find(int x) { while (parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩 x parent[x]; } return x; } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (sz[rx] sz[ry]) swap(rx, ry); parent[ry] rx; sz[rx] sz[ry]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k limit; for (int i 1; i m; i) { // m 条边读入挂在邻接表上 int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); } for (int i 1; i k; i) { cin attack[i]; removed[attack[i]] true; } // 初始化并查集 for (int i 1; i n; i) { parent[i] i; sz[i] 1; } // 先把从未被打击的点合并起来 int maxBlock 1; for (int i 1; i n; i) { if (!removed[i]) { for (int v : graph[i]) { if (!removed[v]) { unite(i, v); maxBlock max(maxBlock, sz[find(i)]); } } } } if (maxBlock limit) { cout 0 endl; // 一次都不用打击 return 0; } // 逆向添加 int recovered 0; for (int i k; i 1; i--) { int t attack[i]; removed[t] false; recovered; for (int v : graph[t]) { if (!removed[v]) { unite(t, v); maxBlock max(maxBlock, sz[find(t)]); } } if (maxBlock limit) { cout n - recovered endl; return 0; } } cout n endl; // 理论上不会走到这防御性输出 return 0; }注意上面代码里读入时我用了 m但题目中通常直接给边数和打击数你要根据实际输入定义变量我这里用 m 示意。务必先读 n、m、k、limit 再读边和打击顺序顺序反了整个程序直接崩。4. 常见问题与排查技巧实录4.1 WA 了但检查不出逻辑错误很多同学把代码写完后样例过了一提交就 WA而且怎么检查都找不到问题。根据我自己的经验这类题 WA 的原因大概率集中在两个地方。第一个是 size 数组初始化错误。并查集初始化时每个点 size 必须等于 1但逆向添加时被恢复的点也要重新设 size 为 1。如果你在逆向添加时忘记初始化 parent 和 size或者把它们留成了上次合并后的旧值那合并出来的集合大小必然不对答案自然错。这个 bug 非常隐蔽因为代码能跑样例也过了只有大数据才会暴露问题。第二个是 limit 的判断时机没放对。题目里的 limit 是每个连通块人数的上限不是连通块个数上限。有人会把 limit 和连通块数量混为一谈写成了 if (连通块数量 limit)那肯定错得离谱。这种错误多在紧张的时候犯解决办法是拿到题目先手写两个小样例用笔算出预期答案再对着代码走一遍。4.2 TLE 了怎么办如果你用的是朴素的“每次循环遍历所有点找最大连通块”写法n 一旦超过 5000 就会开始卡。解决办法有两个一个是用我之前维护 maxBlock 的方式每次合并时更新最大值把检查降为 O(1)另一个是如果你坚持遍历也至少要在 find 的时候带上路径压缩别反复递归导致栈溢出。还有一个小提示如果图特别大但打击序列特别短逆向添加时其实不需要从头把所有边都遍历一遍。你可以先只处理那些从未被打击的点之间的边等逆向循环时再处理被打击点的边这样初始构建图的时间也能省一部分。这个属于常数级优化但对卡时限的题目有帮助。4.3 边界数据的坑这类题目特别喜欢出边界数据最常见的两个坑是k 0一次都不打击和 k n所有点都被打击。k 0 时逆向循环根本不会执行你要在预处理阶段就直接判断当前图是否满足 limit如果满足输出 0否则理论上不存在合法方案但题目一般保证有解。k n 时逆向循环会一直执行到 i 1最后一次添加完所有点后连通块就是整张图maxBlock 肯定超过 limit所以也会输出 n打击所有点。这个边界如果你不单独处理有可能越界访问 attack[0]引发 RE。另外如果题目给的图本身存在重边或自环邻接表里会出现重复边合并时 find 两次返回相同根直接 return 即可不影响正确性。但如果你用矩阵存图重边会导致计数混乱这也是我推荐用邻接表的原因。4.4 一个真实的调试经历我去年带一个学弟做这道题他代码写得很工整但样例过了交上去 60 分。我让他把错误数据和正确数据都打出来对比发现他错在一个很不起眼的地方他的 find 函数用了递归但递归层数在链状并查集下能达到 n导致栈溢出小数据看不出来大数据直接崩。后来改成 while 循环加路径压缩马上 AC。这个案例说明并查集实现一定要用迭代版或者在编译选项里开大栈否则极端数据会给你颜色看。5. 经验心得这道题教会我的三件事5.1 逆向思维是信息学奥赛的“万能钥匙”之一P1386 这道题最宝贵的价值不是并查集本身而是“逆向操作”这个思维模型。其实信息学奥赛里有一类题正着做需要删除、拆分、撤销几乎没法下手但只要倒过来看就变成添加、合并、还原配合并查集或者栈就能轻松解决。这种题在提高组复赛里反复出现比如一些带删除操作的图论题、带撤销的 DP 题核心套路都一样顺着读题逆着求解。刷完这道题之后我建议你立刻去找几道类似的题目巩固比如经典的“修复公路”、一些带断边的图连通性题都用逆向并查集做一遍。做过 5 道以上这种题你再遇到类似问题会在十秒内反射性地问自己“这题能不能倒着做”这个反射就是刷题经验积累出的条件反射。5.2 复杂度计算要算到最坏情况很多新手写代码之前不算复杂度写完一跑超时了才开始找优化。我自己的习惯是动手前先估算一下 n、m、k 的上限再算一遍最终算法的最坏复杂度。比如这道题如果你选择了逆向并查集最坏情况就是每个点都添加一次每次添加合并所有邻边总复杂度 O(n m kα(n))这个量级在任何时限内都很安全。但如果你没想清楚就写很可能写出 O(nk) 的版本然后被大数据卡到超时。建议你每次刷题都在代码开头注释里写上“复杂度 O(n m k*α(n))空间 O(nm)”这既是对自己的提醒也是刷题笔记的素材。5.3 手写小样例比任何调试器都管用这道题有一个特点数据规模不大时完全可以在纸面上模拟整个过程。我每次遇到新题都会画一个 5 个点 6 条边的小图手动跑一遍题目描述的流程把每一步的连通块状态记下来。这个习惯能帮我快速理解题意、验证思路更能在代码写完后用同一个样例校验结果。如果手算答案和程序输出对不上就逐行对比往往很快能定位 bug。我在做 P1386 时用 4 个点 3 条边的小样例成功找出了“初始化时未合并未打击点之间边”的错误。最后再分享一个小技巧O(n m k*α(n)) 这个复杂度看着很唬人其实 α(n) 几乎可以忽略不计你只需要估算 n m k 是否在 10^7 以内。信息学奥赛覆盖到的竞赛环境单点时限一般 1 到 2 秒常数小的话10^7 级别的操作完全无压力超过 10^8 就要警惕了。把复杂度这块基本功打牢P1386 这种题就很难困住你。
P1386 打击犯罪：并查集+逆向思维破解图论连通问题
1. 项目概述与题目定位1.1 这道题到底在说什么“打击犯罪(black)信息学奥赛一本通- P1386”光看名字有点唬人但实际拆开来看就是一道典型的图论连通性问题。题目背景设定是有 n 个犯罪团伙团伙之间存在联系警方需要按顺序打击掉某些团伙每次打击后都要判断剩下的团伙是否能被划分成若干个“安全”的集合每个集合内部的团伙之间仍然保持连通而且每个集合的规模不能超过某个上限。这种“删点后判断连通块大小”的套路在信息学奥赛里出现频率相当高。很多同学第一次看到这道题第一反应是“直接模拟打击过程每次删掉一个点然后跑一遍 DFS 或并查集统计连通块”。这个思路本身没错但如果你真按这个顺序正着做十有八九会超时因为每次删点都要重建整张图的连通关系复杂度是 O(n*m) 级别n 到 1000 或者更大的时候直接卡死。这道题的核心考点其实就是“正难则反”——把删除操作倒过来看成添加操作用并查集从后往前合并这样单次合并接近 O(1)整体复杂度大幅下降。1.2 适合谁来刷这道题如果你正在备战信息学奥赛提高组也就是常说的 S 组复赛这道题属于必须吃透的基础题。它考察的内容非常典型并查集、离线逆向处理、连通块维护这些几乎是提高组初赛复赛的“送分题大户”。尤其是 2026 年山东省信息学奥赛 S 组复赛这类比赛临近的时候把 P1386 这类题目刷明白比盲目刷一堆偏题怪题更有价值。如果你只是刚学完并查集基础想找一道稍微有点弯弯绕绕的题目练手这道题也非常合适。它没有复杂的图论算法不需要树链剖分或者 LCA 这些东西只要把并查集的路径压缩和按秩合并搞清楚再想通“逆向添加”这个思维点基本就能 AC。我自己当年刷这道题的时候最大的收获并不是学会了某个高深算法而是真正理解了“操作顺序”对算法复杂度的影响——这个思维习惯后来在好几道题里都救过我。2. 题目思路拆解为什么正着做会死磕倒着做就通了2.1 正向暴力模拟的复杂度陷阱我们先来看正向思路的直观逻辑。题目告诉你警方会按顺序打击 k 个团伙每次打击后你需要判断剩余团伙能不能满足“每个连通块大小不超过 limit”这个条件。最朴素的做法是每次打击后遍历所有剩余点DFS 或 BFS 找连通块统计每个连通块的点数然后检查是否都小于等于 limit。假设有 n 个点m 条边打击 k 次每次都要 O(nm) 地重建连通关系总复杂度就是 O(k*(nm))。如果 n 和 m 都到了 1000 这个量级k 也接近 n那运算次数轻松破百万甚至千万在信息学奥赛的时限下很容易 TLE。更关键的是正向做有一个绕不开的麻烦删点操作在并查集里非常难实现。并查集本身是支持“合并”的你没法高效地把一个集合拆开除非用可撤销并查集或者 LCT 这种高级结构那就严重超纲了。这时候就要想到“时间倒流”这个技巧。你把整个打击序列倒过来看最后一次打击后的状态其实就是所有没被打击过的点组成的图而最后一次打击之前的状态等价于在这个基础上把最后一个被打击的点“加回去”。也就是说正向删除的逆操作是逆向添加而添加操作完美匹配并查集的合并语义。于是问题从“每次删点统计连通块”变成了“每次加点并合并相邻边统计连通块大小”复杂度降为排序边 k 次合并的级别。2.2 题目数据的隐藏规律与二分答案陷阱这道题还有一个容易让新手懵的地方题目给的 limit 并不是固定的而是跟打击次数相关。有的版本里警方希望“至少有多少个团伙被打击才能让剩下的每个连通块都不超过 limit 人”。这时候答案可能具有单调性——打击越多剩下的点越少连通块规模只会变小或不变不会变大。既然有单调性很多同学立刻想到二分答案每次二分打击数量 mid然后判断打击后是否满足条件。二分答案本身是没错的但如果你还是正向模拟“每次二分都重新跑一遍图”那么一次判断 O(nm)加上二分 O(log n) 次总复杂度勉强能接受可是实现起来非常容易出错。尤其是边界条件比如“恰好打击到第几个才算满足”“打击数量为 0 时是什么情况”稍不留神就会 WA。其实这道题更优雅的做法是直接用逆向思维配合并查集一次性扫描出临界点不需要二分。怎么判断你从最后一个时刻往前添加点同时记录每个连通块的大小一旦发现某个连通块大小超过了 limit说明在这个时刻之前的状态还不满足条件继续往前添加当所有连通块大小都满足不超过 limit 时此刻的“已添加点集合”就是最后一次合法状态用总点数减去已添加点数量就是最少需要打击的团伙数。这两个思维点——逆向操作 单调性利用——是整套代码的灵魂。理解了它们P1386 就不再是难题而是一道“换了一层皮的并查集模板题”。3. 核心算法与代码实现3.1 并查集基础回顾在写这道题之前有必要花一分钟快速过一遍并查集的关键点。并查集我们一般用 parent 数组记录每个节点的父节点用 size 数组或 rank 数组记录集合大小或深度。find(x) 函数负责找到 x 的根节点路径压缩就是在查找过程中把沿途节点直接挂到根上这样下次查找就 O(1) 了。union(x, y) 函数把 x 和 y 所在集合合并合并时可以让较小的集合挂到较大的集合下面也就是按秩合并保证树的高度尽量小。int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (size[rx] size[ry]) swap(rx, ry); parent[ry] rx; size[rx] size[ry]; }路径压缩加上按秩合并单次操作的均摊复杂度是反阿克曼函数基本可以认为是常数级。这就是并查集能在这道题里充当主力算法的底气。注意 size 数组在这里不只是为了按秩合并它本身也承载了“统计连通块大小”的业务逻辑所以初始化时每个点的 size 都要设为 1。3.2 如何存储图和打击顺序拿到题目后先别急着写代码先把数据读进来理清楚。你需要存储这张无向图通常用邻接表 vector graph[n1] 存每条边。同时题目会给你一个打击顺序数组 attack[1..k]记录每次打击哪个点。还有每个团伙的人头数这个数据可能用 weight 数组存也可能直接用点编号作为大小具体看输入描述。这里有个很关键的细节正向的打击顺序逆向使用时需要倒过来遍历。比如攻击顺序是 3、1、4那么逆向添加顺序就是 4、1、3。你可以用一个数组 reAttack 来存逆向顺序也可以直接在循环里 for (int i k; i 1; i--) 处理。我个人习惯先把所有打击点标记成“已打击”状态从一开始就把这些点从图中禁用然后逆向循环时再逐个启用。bool removed[MAXN]; // 标记点是否已被打击 for (int i 1; i k; i) { cin attack[i]; removed[attack[i]] true; } // 初始时所有未打击的点构成图 for (int i 1; i n; i) { if (!removed[i]) { // 把这个点加入并查集并合并它所有连向未打击点的边 } }3.3 逆向添加的完整流程整个逆向循环分三步走第一步把当前要添加的点 t 标记为未打击并把它自己加入并查集第二步遍历 t 的所有邻接点 v如果 v 当前没有被打击或者已经通过之前的逆向操作被恢复就合并 t 和 v第三步检查所有连通块的最大 size 是否超过 limit如果不超过记录当前已经恢复的点数继续循环。有一个容易踩坑的点初始状态不是“所有点都在并查集里”而是“所有没被打击过的点都在”。所以你在正式逆向循环之前得先把那些从头到尾都没被打击过的点预先加入并查集并合并它们之间的边。否则等到逆向循环时再一个个恢复顺序就乱套了。int recovered 0; for (int i k; i 1; i--) { int t attack[i]; removed[t] false; parent[t] t; size[t] 1; recovered; for (int v : graph[t]) { if (!removed[v]) { unite(t, v); } } // 检查全局最大连通块大小 int maxSize 0; for (int j 1; j n; j) { if (!removed[j] find(j) j) { maxSize max(maxSize, size[j]); } } if (maxSize limit) { cout n - recovered endl; return 0; } }看到这里你可能会有疑问每次循环都要遍历所有点找最大连通块这复杂度不是又变成 O(n*k) 了吗确实上述写法在 n 和 k 都是 1000 时没问题但如果 n 到了 10^5 级别就撑不住了。优化技巧是维护一个全局最大连通块大小的变量 maxBlock每次合并两个集合时新集合大小 size[rx] size[ry]用这个值更新 maxBlock。因为合并只会让连通块变大所以 maxBlock 是单调不减的每次更新只需要比较一次即可完全不需要遍历所有点。3.4 完整代码与注释这里给出一版可 AC 的标准代码加了详细注释方便你直接对着写。注意我用的是 C因为信息学奥赛默认评测环境就是 CC17 实测没问题。#include bits/stdc.h using namespace std; const int MAXN 1005; int parent[MAXN], sz[MAXN]; vectorint graph[MAXN]; bool removed[MAXN]; int attack[MAXN]; int n, k, limit; int find(int x) { while (parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩 x parent[x]; } return x; } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (sz[rx] sz[ry]) swap(rx, ry); parent[ry] rx; sz[rx] sz[ry]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k limit; for (int i 1; i m; i) { // m 条边读入挂在邻接表上 int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); } for (int i 1; i k; i) { cin attack[i]; removed[attack[i]] true; } // 初始化并查集 for (int i 1; i n; i) { parent[i] i; sz[i] 1; } // 先把从未被打击的点合并起来 int maxBlock 1; for (int i 1; i n; i) { if (!removed[i]) { for (int v : graph[i]) { if (!removed[v]) { unite(i, v); maxBlock max(maxBlock, sz[find(i)]); } } } } if (maxBlock limit) { cout 0 endl; // 一次都不用打击 return 0; } // 逆向添加 int recovered 0; for (int i k; i 1; i--) { int t attack[i]; removed[t] false; recovered; for (int v : graph[t]) { if (!removed[v]) { unite(t, v); maxBlock max(maxBlock, sz[find(t)]); } } if (maxBlock limit) { cout n - recovered endl; return 0; } } cout n endl; // 理论上不会走到这防御性输出 return 0; }注意上面代码里读入时我用了 m但题目中通常直接给边数和打击数你要根据实际输入定义变量我这里用 m 示意。务必先读 n、m、k、limit 再读边和打击顺序顺序反了整个程序直接崩。4. 常见问题与排查技巧实录4.1 WA 了但检查不出逻辑错误很多同学把代码写完后样例过了一提交就 WA而且怎么检查都找不到问题。根据我自己的经验这类题 WA 的原因大概率集中在两个地方。第一个是 size 数组初始化错误。并查集初始化时每个点 size 必须等于 1但逆向添加时被恢复的点也要重新设 size 为 1。如果你在逆向添加时忘记初始化 parent 和 size或者把它们留成了上次合并后的旧值那合并出来的集合大小必然不对答案自然错。这个 bug 非常隐蔽因为代码能跑样例也过了只有大数据才会暴露问题。第二个是 limit 的判断时机没放对。题目里的 limit 是每个连通块人数的上限不是连通块个数上限。有人会把 limit 和连通块数量混为一谈写成了 if (连通块数量 limit)那肯定错得离谱。这种错误多在紧张的时候犯解决办法是拿到题目先手写两个小样例用笔算出预期答案再对着代码走一遍。4.2 TLE 了怎么办如果你用的是朴素的“每次循环遍历所有点找最大连通块”写法n 一旦超过 5000 就会开始卡。解决办法有两个一个是用我之前维护 maxBlock 的方式每次合并时更新最大值把检查降为 O(1)另一个是如果你坚持遍历也至少要在 find 的时候带上路径压缩别反复递归导致栈溢出。还有一个小提示如果图特别大但打击序列特别短逆向添加时其实不需要从头把所有边都遍历一遍。你可以先只处理那些从未被打击的点之间的边等逆向循环时再处理被打击点的边这样初始构建图的时间也能省一部分。这个属于常数级优化但对卡时限的题目有帮助。4.3 边界数据的坑这类题目特别喜欢出边界数据最常见的两个坑是k 0一次都不打击和 k n所有点都被打击。k 0 时逆向循环根本不会执行你要在预处理阶段就直接判断当前图是否满足 limit如果满足输出 0否则理论上不存在合法方案但题目一般保证有解。k n 时逆向循环会一直执行到 i 1最后一次添加完所有点后连通块就是整张图maxBlock 肯定超过 limit所以也会输出 n打击所有点。这个边界如果你不单独处理有可能越界访问 attack[0]引发 RE。另外如果题目给的图本身存在重边或自环邻接表里会出现重复边合并时 find 两次返回相同根直接 return 即可不影响正确性。但如果你用矩阵存图重边会导致计数混乱这也是我推荐用邻接表的原因。4.4 一个真实的调试经历我去年带一个学弟做这道题他代码写得很工整但样例过了交上去 60 分。我让他把错误数据和正确数据都打出来对比发现他错在一个很不起眼的地方他的 find 函数用了递归但递归层数在链状并查集下能达到 n导致栈溢出小数据看不出来大数据直接崩。后来改成 while 循环加路径压缩马上 AC。这个案例说明并查集实现一定要用迭代版或者在编译选项里开大栈否则极端数据会给你颜色看。5. 经验心得这道题教会我的三件事5.1 逆向思维是信息学奥赛的“万能钥匙”之一P1386 这道题最宝贵的价值不是并查集本身而是“逆向操作”这个思维模型。其实信息学奥赛里有一类题正着做需要删除、拆分、撤销几乎没法下手但只要倒过来看就变成添加、合并、还原配合并查集或者栈就能轻松解决。这种题在提高组复赛里反复出现比如一些带删除操作的图论题、带撤销的 DP 题核心套路都一样顺着读题逆着求解。刷完这道题之后我建议你立刻去找几道类似的题目巩固比如经典的“修复公路”、一些带断边的图连通性题都用逆向并查集做一遍。做过 5 道以上这种题你再遇到类似问题会在十秒内反射性地问自己“这题能不能倒着做”这个反射就是刷题经验积累出的条件反射。5.2 复杂度计算要算到最坏情况很多新手写代码之前不算复杂度写完一跑超时了才开始找优化。我自己的习惯是动手前先估算一下 n、m、k 的上限再算一遍最终算法的最坏复杂度。比如这道题如果你选择了逆向并查集最坏情况就是每个点都添加一次每次添加合并所有邻边总复杂度 O(n m kα(n))这个量级在任何时限内都很安全。但如果你没想清楚就写很可能写出 O(nk) 的版本然后被大数据卡到超时。建议你每次刷题都在代码开头注释里写上“复杂度 O(n m k*α(n))空间 O(nm)”这既是对自己的提醒也是刷题笔记的素材。5.3 手写小样例比任何调试器都管用这道题有一个特点数据规模不大时完全可以在纸面上模拟整个过程。我每次遇到新题都会画一个 5 个点 6 条边的小图手动跑一遍题目描述的流程把每一步的连通块状态记下来。这个习惯能帮我快速理解题意、验证思路更能在代码写完后用同一个样例校验结果。如果手算答案和程序输出对不上就逐行对比往往很快能定位 bug。我在做 P1386 时用 4 个点 3 条边的小样例成功找出了“初始化时未合并未打击点之间边”的错误。最后再分享一个小技巧O(n m k*α(n)) 这个复杂度看着很唬人其实 α(n) 几乎可以忽略不计你只需要估算 n m k 是否在 10^7 以内。信息学奥赛覆盖到的竞赛环境单点时限一般 1 到 2 秒常数小的话10^7 级别的操作完全无压力超过 10^8 就要警惕了。把复杂度这块基本功打牢P1386 这种题就很难困住你。