I'm having a difficult time explaining/understanding a (seemingly) simple argument of an algorithm that I know I can use to determine if a directed graph G is strongly connected.
The algorithm that I know (does this have a name?) goes like this:
Use BFS (breadth-first-search) on G staring from some node S IF every node is found Construct G^ (G with reversed Edges, G transpose?) Use BFS on G^ starting from the same node S IF every node is found G is strongly connected ELSE G is not strongly connected ELSE G is not strongly connected End
So the first run of BFS ensures that the node S can reach every other node on G, which makes sense. If it cant, then clearly G is not strongly connected.
The second run of BFS on G^, as I understand, will show that any node on the graph can also make it to S in G. This is the part I can't fully explain to myself.
The conclusion of the algorithm I understand, if S can make it to every node and every node can make it to S, then any two nodes will always be able to make it to each other through S.
To reiterate my question, I'm looking for an explanation on why determining S can make it to every node in G^ shows that every node can make it to S in G. I've tried doing a proof by contradiction, but I'm having a hard time wording it out. Any explanation will help me. Thank you!