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.