Finding if a graph is still strongly connected after edge removal

Question

A strongly connected digraph is a directed graph in which for each two vertices 𝑢 and 𝑣, there is a directed path from 𝑢 to 𝑣 and a direct path from 𝑣 to 𝑢. Let 𝐺 = (𝑉, 𝐸) be a strongly connected digraph, and let 𝑒 = (𝑢, 𝑣) ∈ 𝐸 be an edge in the graph. Design an efficient algorithm which decides whether 𝐺 ′ = (𝑉, 𝐸 ∖ {𝑒}), the graph without the edge 𝑒 is strongly connected. Explain its correctness and analyze its running time.

So what I did is run BFS and sum the labels, once on the original graph from 𝑢 and then again in G' without the edge (again from 𝑢) and then : if second sum (in G') < original sum (in G) then the graph isn't strongly connected.

P.S this is a question from my exam which I only got 3/13 points and I'm wondering if i should appeal..

Answer 1

As Sneftel points out, the distance labels can only increase. If u no longer has a path to v, then I guess v's label will be infinite, so the sum of labels will change from finite to infinite. Yet the sum can increase without the graph losing strong connectivity, e.g.,

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

where v's label increases from 1 to 2 because of the indirect path through w.

Answer 2

Since the graph G is strongly connected, G' is strongly connected if and only if there is a path from u to v (this path would replace the edge e).

You can use any path finding algorithm to solve this problem.