1. 这道题到底在考什么第一次看到“删边并查集”这个说法很多人会愣一下。并查集不是只能加边吗怎么还能删边这正是 CodeForces 1303F 这道题最核心的思维拐点。题目大意是给你一个 n×m 的网格初始全是 0然后有 q 次操作每次把某个格子从 0 变成 1每次操作后你要输出当前所有 1 构成的连通块数量。注意这里的“连通”是四连通上下左右相邻才算连在一起。如果你直接每次操作后跑一遍 BFS 或 DFS 去数连通块复杂度是 O(q·n·m)在 n、m 达到 300、q 达到 2×10^6 这个量级下妥妥超时。所以必须换思路。而“删边并查集”这个标签其实说的是把问题反过来看正向是不断加点反向就是不断删点。删点会让连通块数量增加而并查集擅长处理的是合并不擅长处理分裂。那怎么办答案是把删点转化成加边用离线倒序处理。我先把结论摆在这里这道题的标准解法是离线 倒序 并查集。正向操作是“把 0 变 1”倒过来看就是“把 1 变 0”也就是删点。删点会导致连通块分裂但如果我们把时间轴倒过来从最终状态往回推删点就变成了加点加点只会合并连通块并查集就能派上用场了。这个转化是整道题最值钱的地方也是很多人卡住的地方。那为什么标题里写的是“删边并查集”而不是“删点并查集”因为在实际实现中我们通常把每个格子看成一个节点把相邻的 1 之间的边看成连接关系。正向删点等价于删掉这个点以及它关联的所有边倒序加点等价于加入这个点以及它关联的边。所以从边的角度看确实是在做“删边”的逆操作。这个命名虽然有点绕但理解了本质就不纠结了。这道题适合谁看如果你已经会并查集的基本操作但遇到“动态连通性”问题就不知道从哪下手那这道题是极好的训练材料。它不涉及高级数据结构纯粹考思维转化和离线技巧属于那种“想到了就很简单想不到就死活做不出来”的题。接下来我会把整个思考过程、实现细节、踩坑经验全部拆开讲尽量让第一次接触这类题的人也能跟上。2. 为什么正向做不了倒序为什么行2.1 正向操作的死胡同正向来看每次操作是把一个 0 变成 1。这个新出现的 1 可能孤立存在连通块数量 1和上下左右某个已有的 1 连通连通块数量不变同时和多个方向的 1 连通把这些连通块合并成一个连通块数量减少合并的块数 - 1。你会发现正向操作里既有“增加”又有“减少”而且减少的时候需要知道当前这个格子周围有几个不同的连通块。用并查集可以维护合并但问题是并查集不支持“撤销”或者“分裂”。如果某个时刻你需要把一个大连通块拆开并查集就无能为力了。有人可能会想那我每次操作后重新建图跑一遍不就行了复杂度不允许。n×m 最大 9×10^4q 最大 2×10^6乘起来是 1.8×10^11 级别完全不可行。所以正向硬做没有任何出路。2.2 倒序处理的巧妙之处把时间轴倒过来事情就变了。我们先把所有操作全部执行完得到最终状态。然后从最后一次操作开始往前回退每次回退相当于把某个格子从 1 变回 0也就是删掉这个点。删点的时候连通块数量会怎么变假设这个点当前是 1它可能连接了 k 个不同的连通块k 可以是 0 到 4。删掉它之后如果 k 0说明它是孤立的连通块数量 -1如果 k 1说明它只连着一个块删掉后那个块还在连通块数量不变如果 k ≥ 2删掉它之后原来通过它连在一起的那些块会分裂成 k 个独立的块连通块数量增加 k - 1。问题来了删点的时候我们需要知道它周围有几个不同的连通块。并查集可以告诉我们两个点是否在同一个集合里但没法直接告诉我们“周围有几个不同的集合”。而且删点之后并查集里的合并关系没法撤销。那倒序到底怎么用并查集关键在于我们不是真的在倒序过程中维护并查集而是把倒序过程看成加边过程。具体来说我们从最终状态开始把每个格子看成独立节点。然后按照操作的反序每次“恢复”一个格子也就是把它从 0 变回 1同时把它和上下左右已经是 1 的格子合并。这样并查集只做合并不做分裂完美契合。但这里有个细节我们要求的是每次正向操作后的连通块数量。倒序过程中我们得到的是每次“恢复”后的连通块数量这个数量对应的是正向操作之前的状态。所以我们需要把倒序得到的答案再倒回去输出。这个对应关系一定要搞清楚否则答案顺序会全错。2.3 一个生活化的类比你可以把整个过程想象成拆房子和盖房子。正向是不断盖新房子房子之间可能连走廊。盖的时候你可能把几个原本独立的建筑群连成一片也可能只是单独盖了一间。倒过来看就是拆房子拆的时候可能把一个建筑群拆散。但如果我们换一种方式先假设所有房子都已经盖好了然后从最后盖的那间开始一间一间“取消盖房”每取消一间就把它从建筑群里拿掉。但并查集只能加不能减所以更好的方式是从空地开始按照盖房的逆序一间一间把房子“放回去”每放一间就和周围已有的房子连起来。这样并查集始终在做加法连通块数量只会减少或不变维护起来非常干净。这个类比里“房子”就是格子“走廊”就是相邻关系。放回去的顺序就是操作的反序。最终我们得到的连通块数量序列再反转一次就是正向每次操作后的答案。3. 并查集在这里到底怎么用3.1 并查集的基本职责并查集在这道题里只做两件事查询两个格子是否属于同一个连通块合并两个连通块。每次“放回”一个格子时我们把它标记为 1然后检查它的上下左右四个邻居。如果某个邻居已经是 1就尝试合并当前格子和邻居。如果它们原本不在同一个集合合并后连通块总数减 1。如果已经在同一个集合说明它们已经通过其他路径连在一起了不需要重复合并。这里有一个很容易写错的地方四个邻居里可能有多个属于同一个连通块。比如当前格子左边和上边都是 1而且它们本来就通过别的路径连在一起。这时候如果你对每个邻居都做一次“如果不在同一集合就合并”实际上只有第一次合并会生效后面几次查询都会发现已经在同一集合不会重复减。所以逻辑上是安全的但前提是每次合并前都要先判断是否已经在同一集合。3.2 连通块数量的维护初始时所有格子都是 0连通块数量为 0。倒序过程中每放回一个格子连通块数量先加 1因为这个格子本身是一个新块然后每成功合并一次连通块数量减 1。最终得到的数量就是当前状态下 1 的连通块总数。这个维护方式非常直观新加一个点块数 1每连上一条有效的边连接两个不同块块数 -1。因为并查集合并的次数等于有效边的数量所以最终块数 点数 - 有效边数。这也符合图论里连通分量数的计算公式。3.3 时间戳与操作去重这道题有一个坑q 次操作里同一个格子可能被多次操作。但只有第一次从 0 变 1 是有效的后续再操作同一个格子它已经是 1 了不会改变状态。所以我们需要记录每个格子第一次被变成 1 的时间戳。在倒序处理时我们只关心那些“第一次被变成 1”的操作。对于重复操作它们不改变状态对应的答案和上一次有效操作后的答案相同。所以我们可以先正向扫描一遍记录每个格子第一次变 1 的时刻以及每个时刻实际发生状态变化的格子。然后倒序时只处理这些有效变化。具体做法用一个数组first_time[x][y]记录格子 (x,y) 第一次变 1 的操作编号初始为 -1。正向遍历所有操作如果first_time[x][y] -1就设为当前操作编号并把这个格子加入“有效操作列表”。最终状态就是所有first_time ! -1的格子都是 1。倒序时从最后一个有效操作开始依次“撤销”这些格子的 1 状态同时用并查集维护连通块。这样处理之后重复操作就不会干扰倒序过程。对于没有发生状态变化的操作它们的答案直接沿用上一个有效操作的答案即可。4. 完整实现步骤与代码拆解4.1 数据准备与初始化假设网格是 n 行 m 列操作次数是 q。我们把每个格子映射成一个整数编号id x * m y其中 x 从 0 到 n-1y 从 0 到 m-1。这样并查集的父数组大小就是 n*m。int n, m, q; cin n m q; vectorpairint,int ops(q); for (int i 0; i q; i) { cin ops[i].first ops[i].second; ops[i].first--; ops[i].second--; // 转成 0 下标 } vectorvectorint first_time(n, vectorint(m, -1)); vectorint valid_ops; // 存储有效操作的索引 for (int i 0; i q; i) { int x ops[i].first, y ops[i].second; if (first_time[x][y] -1) { first_time[x][y] i; valid_ops.push_back(i); } }这段代码做完之后valid_ops里就是所有真正让某个格子从 0 变 1 的操作编号按时间顺序排列。最终状态就是所有first_time ! -1的格子为 1。4.2 并查集结构定义并查集需要路径压缩和按秩合并保证接近 O(1) 的均摊复杂度。由于节点数最多 9×10^4q 最多 2×10^6并查集操作次数大约是有效操作数乘以 4每个格子检查四个邻居所以总操作量在千万级别必须保证并查集高效。struct DSU { vectorint parent, rank; int components; DSU(int n) : parent(n), rank(n, 0), components(0) { iota(parent.begin(), parent.end(), 0); } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; if (rank[ra] rank[rb]) swap(ra, rb); parent[rb] ra; if (rank[ra] rank[rb]) rank[ra]; components--; return true; } };注意这里的components初始为 0因为一开始没有任何格子是 1。每当我们“放回”一个格子时先components然后每成功合并一次就components--。4.3 倒序处理的核心循环倒序处理时我们从最终状态开始但最终状态并不是一开始就建好的。我们的做法是从空状态开始按照valid_ops的反序依次把格子“放回”。每放回一个格子就把它标记为 1然后检查四个邻居如果邻居已经是 1就合并。vectorint ans(q, 0); DSU dsu(n * m); vectorvectorbool active(n, vectorbool(m, false)); int comp 0; // 从最后一个有效操作开始倒序 for (int i valid_ops.size() - 1; i 0; i--) { int idx valid_ops[i]; int x ops[idx].first, y ops[idx].second; active[x][y] true; comp; int id x * m y; // 检查四个方向 int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 nx n ny 0 ny m active[nx][ny]) { int nid nx * m ny; if (dsu.unite(id, nid)) { comp--; } } } // 此时 comp 对应的是正向第 idx 次操作之前的状态 // 但我们需要的是第 idx 次操作之后的状态 // 所以答案应该记录在 idx 位置但值是 comp ans[idx] comp; }这里有一个关键点倒序处理到第 i 个有效操作时我们放回了这个格子此时comp表示的是“正向第 idx 次操作之后”的连通块数量。因为正向第 idx 次操作就是把这个格子变成 1倒序放回它之后状态正好对应正向操作之后。所以ans[idx] comp是正确的。但对于那些不是有效操作的操作重复操作它们的答案应该和上一个有效操作的答案相同。所以最后还需要填充这些位置。4.4 答案填充与输出int last 0; for (int i 0; i q; i) { if (first_time[ops[i].first][ops[i].second] i) { last ans[i]; } else { ans[i] last; } } for (int i 0; i q; i) { cout ans[i] \n; }这段逻辑是按时间顺序遍历所有操作如果当前操作是某个格子的第一次变 1就更新last为这个操作对应的答案否则说明是重复操作答案就是上一个有效操作的答案。这样就能保证输出顺序和正向操作一致。5. 常见问题与排查技巧实录5.1 答案顺序搞反了这是最容易犯的错误。倒序处理得到的comp对应的是正向操作之后的状态但如果你在倒序循环里直接按顺序存答案最后输出就会是反的。我建议的做法是在倒序循环里把答案存到ans[idx]其中idx是正向操作编号。这样最后按 0 到 q-1 输出就是正确顺序。如果你发现输出的答案整体是倒过来的那八成是这里搞错了。检查一下你的答案数组索引是不是用了倒序循环的计数器而不是正向操作编号。5.2 重复操作处理不当题目里同一个格子可能被操作多次。如果你不处理重复操作倒序时可能会把一个已经是 1 的格子再次“放回”导致comp多加了一次或者并查集重复合并。正确的做法是只记录第一次变 1 的时间戳倒序时只处理这些有效操作。还有一个细节如果某个格子从未被操作过它始终是 0不需要处理。最终状态里只有那些first_time ! -1的格子是 1。5.3 并查集合并时重复减在检查四个邻居时如果多个邻居属于同一个连通块你可能会多次合并。但并查集的unite函数在发现两个节点已经在同一集合时会返回 false不会执行合并也不会减comp。所以只要你的unite实现正确就不会重复减。但如果你自己手动判断“如果邻居是 1 就 comp--”那就错了。必须通过并查集的合并结果来决定是否减。5.4 边界条件与数组越界网格的边界处理很容易出错。检查邻居时一定要判断nx 0 nx n ny 0 ny m。另外格子编号id x * m y要保证唯一且不越界。如果 n 和 m 比较大注意用int还是long long。这道题里 n*m 最大 9×10^4int 完全够用。5.5 内存与时间优化q 最大 2×10^6操作数组和答案数组都是这个量级。用vector动态分配没问题但要注意不要用vectorvectorint存二维时间戳那样内存开销大。可以用一维数组first_time[x * m y]来代替节省内存和访问时间。并查集的路径压缩建议用递归写法虽然递归有栈开销但路径压缩后树高很低实际运行很快。如果担心栈溢出可以改成迭代写法。问题现象可能原因排查方法答案整体倒序答案存储顺序错误检查是否用正向操作编号存答案某些操作答案偏大重复操作未去重检查 first_time 数组是否正确记录连通块数量偏小合并时重复减检查是否依赖 unite 返回值程序崩溃数组越界检查边界判断和 id 计算超时并查集未优化检查路径压缩和按秩合并5.6 一个容易被忽略的细节倒序处理时我们是从最后一个有效操作开始依次往前。但最终状态并不是一开始就全部 active 的。我们的做法是从空状态开始按照有效操作的反序一个一个把格子加回去。这意味着在倒序循环开始时active全是 falsecomp是 0。然后每处理一个有效操作就把它对应的格子设为 active并合并邻居。这样处理完所有有效操作后active状态正好对应正向第一次操作之前的状态也就是全 0。这个逻辑是自洽的但第一次写的时候容易绕晕。你可以这样验证假设只有一个有效操作把 (0,0) 变成 1。倒序循环只执行一次放回 (0,0)comp 变成 1ans[0] 1。正向看操作后只有一个 1连通块数量是 1正确。如果有两个有效操作先 (0,0) 后 (0,1)。倒序先放回 (0,1)comp1ans[1]1再放回 (0,0)发现右边 (0,1) 是 active合并comp 先加 1 变成 2合并后减 1 变成 1ans[0]1。正向看第一次操作后只有 (0,0)块数 1第二次操作后 (0,0) 和 (0,1) 连在一起块数还是 1。答案正确。6. 从这道题能学到什么通用套路6.1 离线倒序是处理删边问题的利器并查集只能加边不能删边这是它的天然局限。但很多问题正向看是删边倒过来看就是加边。只要问题满足“操作可逆”且“最终状态容易确定”就可以考虑离线倒序。这道题就是典型正向是加点倒序是删点但删点会导致分裂所以再转化一步把删点看成加边并查集就能用了。类似的套路还出现在“动态图连通性”“区间删除”“历史版本查询”等问题里。核心思想都是把时间轴倒过来让不可逆操作变成可逆操作。6.2 连通块数量的维护公式连通块数量 节点数 - 有效边数。这个公式在并查集维护连通性时非常有用。每加入一个节点节点数 1每合并两个不同集合有效边数 1连通块数量 -1。只要记住这个公式维护逻辑就不会乱。在这道题里节点数就是当前 active 的格子数量有效边数就是成功合并的次数。comp的增减完全遵循这个公式。6.3 时间戳去重是处理重复操作的通用方法很多题目里操作可能重复但只有第一次有效。用一个first_time数组记录每个位置第一次被操作的时间后续重复操作直接忽略。这个方法在“染色问题”“覆盖问题”“状态翻转问题”里都很常见。关键是要区分“有效操作”和“无效操作”并在输出时正确填充无效操作的答案。6.4 网格图转一维编号的技巧网格问题里把二维坐标转成一维编号可以简化并查集的操作。id x * m y是最常用的映射方式。注意 x 和 y 的范围以及 m 是列数。如果网格是 n 行 m 列那么 id 的范围是 0 到 n*m-1。这个技巧在几乎所有网格并查集问题里都会用到。6.5 复杂度分析与优化方向这道题的时间复杂度是 O((nm q) * α)其中 α 是并查集的反阿克曼函数近似常数。空间复杂度是 O(nm q)。对于 n,m ≤ 300q ≤ 2×10^6这个复杂度完全可以接受。如果你发现超时优先检查并查集是否写了路径压缩和按秩合并。其次检查是否有不必要的二维数组访问。最后检查输入输出是否用了ios::sync_with_stdio(false)加速。7. 我个人在实际操作中的几点体会第一次做这道题的时候我卡在“删边并查集”这个说法上很久。我一直在想并查集怎么能删边后来才反应过来所谓的删边并查集并不是真的在并查集里删边而是通过离线倒序把删边转化成加边。这个思维转化是整道题的分水岭。另一个让我踩坑的地方是答案顺序。我一开始在倒序循环里直接把comp存到答案数组里结果输出完全是反的。后来改成用正向操作编号索引才正确。这个细节看起来小但调试起来很费时间建议一开始就写对。还有一次我忘了处理重复操作导致同一个格子被多次放回comp被多加了好几次。后来加了first_time数组去重才解决。这个坑也很典型凡是涉及“状态变化”的题都要先想清楚哪些操作是真正改变状态的。最后说一个性能上的小技巧并查集的find函数用递归写路径压缩在数据量大的时候可能栈开销比较大。如果担心这个问题可以改成迭代写法用循环找到根节点然后再走一遍把路径上的节点都指向根。这样虽然代码稍微长一点但更稳。这道题整体难度中等偏上思维难度大于实现难度。如果你能独立想出离线倒序的思路并正确处理重复操作和答案顺序那说明你对并查集和离线技巧的掌握已经比较扎实了。后续可以再找一些“动态连通性”“删边问题”的题目练手比如带时间戳的并查集、可持久化并查集等逐步提升。