检测支持增删边的无向图中两节点连通性的最优方法

嘿，这个动态无向图的连通性检测问题挺经典的，我来分享下最适合的实现思路！

咱们要处理三种在线操作：

• add x y：给无向图的节点x、y加一条边
• remove x y：删除x、y之间的边（无效操作直接忽略）
• is linked x y：判断x、y是否在同一个连通分量里（是否有路径）

首先得说哪些方法不适合这个场景：

• DFS/BFS逐次判断：每次is linked都遍历图，时间复杂度O(V+E)，图规模大的时候完全没法用，效率极低。
• 普通并查集（DSU）：虽然add和is linked能做到近似O(α(V))的高效时间，但不支持删除边——并查集的合并操作是不可逆的，除非你用带撤销的版本，但那只支持按顺序撤销（栈式操作），没法处理任意的remove请求，所以在线场景下直接pass。

这是专门针对动态无向图连通性设计的高效数据结构，基于平衡二叉搜索树（比如Splay Tree）实现，所有操作的时间复杂度都是O(log V)，完美匹配需求：

基本原理 #

ETT把每个连通分量（树）的欧拉路径用一棵平衡BST来表示。欧拉路径就是遍历树时，每次进入或离开节点都记录一次，这样每个边会被记录两次（进入和离开）。通过维护这些BST，我们可以快速实现：

1. add x y：先判断x和y是否已经连通（用ETT的根节点是否相同来判断），如果不连通，就把两个连通分量对应的ETT合并，时间O(log V)。
2. remove x y：
   • 先做有效性检查：用哈希表维护的节点集合确认x、y存在，再用邻接表确认x、y之间有边。
   • 确认有效后，找到这条边在欧拉路径中的两次记录，拆分对应的ETT，完成删边操作，时间O(log V)。
3. is linked x y：只需要判断x和y所在的ETT根节点是否相同，时间O(log V)。

工程实现的辅助结构 #

为了配合ETT，你还需要两个辅助结构：

• 一个哈希集合（比如unordered_set<int>）：用来快速判断某个节点是否存在于图中，处理remove的无效情况。
• 一个邻接表（比如unordered_map<int, unordered_set<int>>）：用来快速检查两个节点之间是否存在边，避免无效的remove操作。

LCT原本是用来处理动态树的路径查询问题，但也可以用来实现无向图的动态连通性。不过相比ETT，LCT更偏向于有根树的操作，对于无向图连通性的处理不如ETT直接，但同样能做到O(log V)的时间复杂度，适合已经熟悉LCT实现的场景。

如果是在线场景（逐行处理操作，无法提前知道所有操作顺序），欧拉游树（ETT）是最优选择，所有操作都能做到对数时间复杂度，完美适配三种操作需求。如果是离线场景（可以先收集所有操作再处理），可以用带时间戳的并查集来处理删除，但在线场景下ETT是不二之选。

内容的提问来源于stack exchange，提问作者Guangyi Tao