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.