algorithm - 检测图形何时被分解为两个或多个连接的组件

Question

我最近一直在思考一个计算机科学问题，我很想听听其他人的反馈:

假设您有一个 3d 方 block 世界(例如我的世界)。如果对于任何 block ，从该 block 到最底部的一排 block 都存在一条可靠的路径，则世界是“稳定的”。当世界生成时，它保证是稳定的，但随着玩家四处挖掘方 block ，他们可能会使世界变得不稳定。例如，玩家可以挖出一棵树的树干，这样树顶就会悬在半空中，世界就不稳定了。

目标是快速确定世界是否因挖掘而变得不稳定，以及应该移除哪些立方体以使世界恢复稳定状态。该算法应该是快速的，并且在正在进行许多挖掘的世界环境中工作，其中大部分不会使世界变得不稳定。

一种天真的方法是在挖掘后获取每个相邻的立方体并找到通往地球底部的路径。如果您无法从任何邻居找到通往底部的路径，那么世界现在就不稳定了(并且您还知道在这个过程中要移除哪些立方体)。当到达底部的路径很长时，这种情况就会分崩离析。很容易想出一个计算成本高昂的例子(想象一下移除大型螺旋塔的顶部)。

这个问题可以被认为是一个图问题，您想要快速检测单个顶点是否可以将图分成两个或更多部分。

我很想知道是否有人有其他想法来解决这个问题。

Answer 1

Link/cut tree可能会帮助你。 Daniel Sleator , 关于该结构的作者 shared his solution到 similar problem .看his comments on codeforces.ru您可能会发现它们很有用。

我会在这里写下我的想法。让我们在底层下创建一个顶点。该顶点是您建筑物的地下室。将 basement_vertex 与底层的所有顶点连接起来。从底层顶点运行深度优先搜索 (DFS)。此 dfs 将生成有根树。这棵树应该是某个链接切割树的基础(初始阶段)。

更新

Link-Cut Trees 只有在给定的图是树时才有效。对于任何 图，我们必须解决动态连接问题。 Here有关动态连接问题的更多信息。