algorithm - 查找边缘去除后图是否仍然是强连接的

Question

强连通有向图是一个有向图，其中对于每两个顶点 和 ，都有一条从 到 的有向路径和一条从 到 的直接路径。令 = (, ) 为强连通有向图，令 = (, ) ∈ 为图中的一条边。设计一个有效的算法来判断 ' = (, ∖ {})，没有边的图是强连通的。解释其正确性并分析其运行时间。

所以我所做的是运行 BFS 并对标签求和，一次在原始图上，然后在没有边缘的 G' 中再次（再次从 ），然后：如果第二个总和（在 G' 中）< 原始总和（在 G 中）然后该图没有强连接。

PS 这是我考试中的一个问题，我只得到了 3/13 分，我想知道我是否应该上诉..

Answer 1

正如 Sneftel 指出的那样，距离标签只会增加。如果u不再有到 的路径v，那么我猜v的标签将是无限的，因此标签的总和将从有限变为无限。然而，总和可以增加而不会失去强大的连接性，例如，

u<----->v
 \     /|
  \|  /
    w

wherev的标签从 1 增加到 2 因为间接路径通过w。

Answer 2

由于图G是强连通的，G'是强连通的当且仅当存在从u到v的路径（该路径将替换边e）。

您可以使用任何寻路算法来解决此问题。