是否存在支持节点/边增删的动态图连通分量稳定查找算法

存在支持节点/边全动态增删的连通分量查找算法，这类问题属于经典的动态图连通性研究范畴，和静态图、仅支持增量添加的半动态图场景不同，全动态场景的算法选型需要结合是否能提前获取所有操作序列（离线/在线）、删操作占比、性能要求综合选择。

离线场景：线段树分治 + 可撤销DSU #

这是工业界最常用、实现性价比最高的方案，适用前提是可以提前拿到全部的增删操作序列，不需要即时响应每一步的在线查询。

• 核心逻辑：
  1. 先遍历所有操作，记录每条边、每个节点的存活时间区间（从添加的时间点到删除的时间点，节点删除等价于该节点关联的所有边同步删除）
  2. 以时间轴为范围建线段树，把每条边挂载到它存活区间对应的线段树节点上
  3. DFS遍历线段树：进入节点时，用不做路径压缩、仅按秩合并的可撤销DSU把当前节点挂载的所有边执行合并，用栈记录每一步合并的修改；递归遍历完当前节点的所有子节点后，弹栈撤销当前节点做的所有合并操作，回溯到父节点状态
  4. 遍历到线段树叶子节点时，当前DSU的状态就是对应时间点的图状态，可以直接查询连通分量计数、两点连通性
• 复杂度：单步操作/查询的平均时间复杂度为O(logN * logM)，N为节点总数，M为总操作数，常数极低，实现难度小。

在线场景：实时响应增删查操作 #

如果无法提前获取后续操作序列，需要每一步操作后即时返回正确结果，有以下几类成熟方案：

• 基于欧拉环游树（ETT）的全动态连通性结构
  用平衡树维护图的生成森林的欧拉环游序列，支持动态插入边、删除边、查询两点连通性，原生支持全动态操作，经优化后单步操作均摊复杂度可达O(log²N)，缺点是实现复杂度极高，代码量大，运行常数高，工业界很少直接从零实现。
• Link-Cut Tree（LCT，链接切割树）方案
  用实链剖分维护动态生成树，原生支持树边的链接、切断、链查询，单步操作均摊复杂度O(logN)；但处理非树边的删除时，需要额外维护候选替换边集合，整体实现复杂度和ETT接近。
• 工程折中方案
  如果删操作占比不高，不需要严格最坏复杂度保证，可以选择实现难度更低的折中方案：
  • 带时间戳的惰性DSU：给每条边、父节点指针记录过期时间，查询连通性时跳过已删除的边，每隔一定操作次数重建一次DSU做路径压缩，在删操作占比低于10%的场景下，性能接近普通增量DSU。
  • 分块DSU：把操作按固定大小分块，块内删操作通过回滚块内的DSU合并记录处理，块间做预计算，平衡实现难度和运行效率，是很多工程场景的首选。

带路径压缩、按秩合并的普通DSU之所以无法支持删操作，本质是路径压缩过程中会丢失原始的父子层级信息，删除操作无法快速回溯修改；所有支持删操作的DSU变体都会放弃全局路径压缩，改用可回滚的结构，必然带来一定的复杂度上升。目前不存在全动态场景下能达到增量DSU那种O(1)均摊复杂度的连通性算法，所有方案都有对数级别的复杂度开销。

内容的提问来源于stack exchange，提问作者Gagan Walia