algorithm - 在删除连接子图的节点后确定剩余的子图

Question

所以我在尝试实现一个功能时遇到了这个问题：
假设我有一个随机的、无向的节点图，其中一些节点相互连接。
让我们沿着某个路径将可以从彼此到达的每一组节点称为一个集合。
现在，假设图只包含一个这样的集合（即，每个节点都可以从其他节点访问）。
如果我取一个随机节点a并将其从集合中移除，我需要快速有效地确定哪些集合仍然存在如果a是集合中的一个切点，则移除它应将集合拆分为两个或多个较小的集合。我只需要一个有效的方法来做两件事：
从集合中移除并确定剩余集合，以及
添加一个新节点b，其中有任意数量的新边将其连接到其他节点。
我需要能够适度快速地执行这两个操作实际上，我在寻找一个o（log n）或o（1）的解决方案。不接受O（N）解，因为此图可能很大。我并不特别关心内存开销有谁能给我指出在这里使用哪种数据结构/算法的正确方向吗？我已经考虑过像Union Find和Djikstra这样的东西，但它们不适合我的需要。我不想每次添加或删除节点时都对整个图运行完全连接检查。

Answer 1

有一个非常好的paper by Henzinger and King。我想它能直接回答你的问题。
该方法已经删除了一个边（删除一个顶点等于删除所有对它的边缘的删除）和O（log（n）/LOGLOG（n））每个查询的最坏情况复杂度（在相同的连接组件中是V和U）的摊销O（log ^ 3（n））复杂度。
此外，此问题有许多变体，例如，如果只允许删除，则可以更快地执行此操作。