标准Disjoint Set Union（DSU）只擅长处理集合合并，没法直接拆分集合，所以碰到频繁删边的场景，得换两种思路来解决：

一、离线场景：时间倒流法（基于DSU，易实现） #

如果所有增删边操作能提前拿到，这方法最划算——把删边转成DSU能搞定的加边操作：

• 步骤1：把所有操作记下来，同时找出最终状态里剩下的所有边；
• 步骤2：初始化DSU，把最终状态的边全加进去，算出此时的连通分量数；
• 步骤3：从最后一步操作倒着往回处理：
  • 原操作是删边？那倒过来就是加边，用DSU合并两个顶点的集合，要是原本不连通，连通分量数就减1；
  • 原操作是加边？只要标记这条边不在最终状态里，不用管它；
• 步骤4：把倒序记录的结果反过来，就是原操作每一步的连通分量数。

你的示例实操： #

原操作流程：

1. 初始边集 E = {(1, 2), (2, 3), (4, 5)}，连通分量数为2；
2. 加边 (3, 4)，边集变为 E' = {(1, 2), (2, 3), (4, 5), (3, 4)}，分量数为1；
3. 删边 (2, 3)，边集变为 E'' = {(1, 2), (4, 5), (3, 4)}，分量数为2。

离线处理过程：

• 先处理最终状态E''，把这些边加入DSU，此时分量数是2（对应原第3步的结果）；
• 倒着处理原第3步（删边(2,3)）：转成加边，合并2和3的集合，原本不连通，分量数变1（对应原第2步的结果）；
• 倒着处理原第2步（加边(3,4)）：标记这条边不在初始状态，不用处理，此时分量数是2（对应原第1步的结果）；
• 把结果反转：2 → 1 → 2，和实际情况完全一致。

二、在线场景：Link-Cut Tree（动态树） #

要是操作没法提前知道，得实时处理，就用Link-Cut Tree（动态树结构），它支持三个关键操作：

• link(u, v)：给两个不连通的顶点加边，成功的话分量数减1；
• cut(u, v)：删掉u和v之间的边，要是原本连通且删完后分成两个分量，分量数加1；
• is_connected(u, v)：判断两个顶点是否连通（辅助判断用）。

你的示例实操： #

• 初始状态：每个顶点单独成分量，总数是5；
• 加初始边(1,2)：1和2不连通，分量数减1→4；
• 加初始边(2,3)：2和3不连通，分量数减1→3；
• 加初始边(4,5)：4和5不连通，分量数减1→2；
• 加边(3,4)：3和4不连通，分量数减1→1；
• 删边(2,3)：2和3原本连通，删完后分裂，分量数加1→2；
• 每一步都能直接拿到当前的连通分量数。

总结 #

• 时间倒流法靠DSU就能实现，速度快，但必须提前知道所有操作；
• Link-Cut Tree能处理动态在线操作，但代码实现复杂度高，得懂树链剖分相关知识。

内容的提问来源于stack exchange，提问作者Nitaa a