Strongly Connected Components of a graph

49 Views Asked by At

I am reading about the Kosaraju-Sharir Algorithm. How does having the reverse postorder and postorder of a DFS tree help you identify strongly connected components? According to HackerEarth, reversing the order somehow helps you identify sinks, but I don't understand why.

1

There are 1 best solutions below

0
On BEST ANSWER

In case other people are curious - I found an interesting comment in Sedgewick's Algorithms:

enter image description here

Not a full answer by any means, but I thought it might help.