Strongly Connected Components Quastion

Question

If you don't know how SCC algorithm works read this article: https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/ (This is the best article I could find).

After finding finish time for each node, we reverse the original graph and start to run DFS from highest time node. What if we start to run DFS from smallest node in the original graph? Why it doesn't work?

Answer 1

Thats because the first DSF's finish times give you the topological order (which means one edge depends on another). SCC means the every nodes are reachable from every other nodes in the component. If you start from the smallest node (so backward) the algorithm will give false result, because in the transposed graph somewhere it wont find a way between two nodes which actually connect, or find an incorrect way because you 'walk throught' a node before its 'parent'.

Simple example (-> means depend on). Start from X the topological order: X,Y,Z,W

X -> Y   ->  Z
^   /
 \ ˘
  W

If you transpose the one above and start from Z, it will look like the whole graph is one SCC. But it is not. You must process the parent element before child. So if you start from X you cannot go into Z in the original graph before Y, also cannot go into W before Y. In the transposed graph there are a route between Z and Y but you can only use it if the invere was there in the original graph. And TO describe that there was or wasnt it. If a node topologically preceed another route and there is a route in the transposed graph between them then they strongly connected.