查询检查删除边缘/节点后 2 个节点之间是否有路径

Question

问题：

给定一个有N个节点和M条边的无向图。给定Q个查询，有两种类型的查询：

• 1-A-B-U-V

移除边缘U-V 后，检查节点a和B之间是否有路径

• 2-A-B-X

删除节点X 后，检查节点a和B之间是否有路径

限制条件：

N <= 100000
M <= 500000
Q <= 100000

p/S:

我认为移除后A和B之间存在路径的唯一方法是A、B在同一个双连通组件中，或者边/节点不是桥/弧。

但由于每个查询只有logN时间(因为最多有100000个查询)，我找不到检查a、B是否在O(logN)中的同一个双连通组件中的方法。

有办法做到吗？或者这个问题有不同的解决方案吗？

Answer 1

实现这一点的简单方法是深度优先搜索，从a开始，如果到达B则停止并返回true，如果无法到达B则返回false。

在几秒钟内了解您的实际性能要求会很有用。

PathFinder图论引擎可以检查两个随机节点是否连接在一个包含403394个节点和3387388个链路的图中，平均时间为0.14秒(100次不同随机节点的测试)

你的图形大约小4到10倍，所以我想它可以在不到十分之一秒的时间内完成。

对于100000个查询，这将不到3小时。

您必须发布测试图，以获得更准确的性能度量。