查找图在删除边后是否仍然是强连接的
Finding if a graph is still strongly connected after edge removal
强连通有向图是一个有向图，其中对于每两个顶点 和 ，
有一条从 到 的有向路径和一条从 到 的直接路径。设 = (, ) 为
强连通有向图，设 = (, ) ∈ 为图中的一条边。
设计一个有效的算法来决定是否
′ = (, ∖ {}), 图
没有边是强连接的。解释其正确性并分析其运行ning
时间.
所以我所做的是 运行 BFS 并对标签求和，一次在原始图上，然后再次在没有边缘的 G' 中（再次从 ）
然后：如果第二个总和（在 G' 中）< 原始总和（在 G 中）则该图不是强连接的。
P.S这是我考试的一道题，我只得了3/13分，我想知道我是否应该上诉..
因为图G是强连通的，所以G'是强连通的当且仅当有一条路径从u 到 v（此路径将替换边 e）。
你可以使用任何寻路算法来解决这个问题。
正如 Sneftel 指出的那样，距离标签只能增加。如果u不再有通往v的路径，那么我猜测v的标签将是无限的，因此标签之和将从有限变为无限。然而，总和可以增加而图表不会失去强连通性，例如，
u<----->v
\ /|
\| /
w
其中 v 的标签从 1 增加到 2，因为通过 w 的间接路径。
强连通有向图是一个有向图，其中对于每两个顶点 和 ， 有一条从 到 的有向路径和一条从 到 的直接路径。设 = (, ) 为 强连通有向图，设 = (, ) ∈ 为图中的一条边。 设计一个有效的算法来决定是否 ′ = (, ∖ {}), 图 没有边是强连接的。解释其正确性并分析其运行ning 时间.
所以我所做的是 运行 BFS 并对标签求和，一次在原始图上，然后再次在没有边缘的 G' 中（再次从 ） 然后：如果第二个总和（在 G' 中）< 原始总和（在 G 中）则该图不是强连接的。
P.S这是我考试的一道题，我只得了3/13分，我想知道我是否应该上诉..
因为图G是强连通的，所以G'是强连通的当且仅当有一条路径从u 到 v（此路径将替换边 e）。
你可以使用任何寻路算法来解决这个问题。
正如 Sneftel 指出的那样，距离标签只能增加。如果u不再有通往v的路径，那么我猜测v的标签将是无限的，因此标签之和将从有限变为无限。然而，总和可以增加而图表不会失去强连通性，例如，
u<----->v
\ /|
\| /
w
其中 v 的标签从 1 增加到 2，因为通过 w 的间接路径。