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..
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.