(Note that my question is different from this one, I understand why we have to do a dfs on a reversed graph, I want to understand why we can't reverse the topological order instead of transposing the graph.)
In Kosaraju's algorithm, it is stated to compute the transposed graph and apply topological sort on it. I understand why this is necessary.
What I don't understand is the necessity to actually compute the transposed graph. Can't we just apply the topological sort algorithm on the original graph and use the resulting list in reverse order?
In Dasgupta,Papadimitriou, Vazirani, one can read
There is not an easy, direct way to pick out a node that is guaranteed to lie in a sink strongly connected component.
I am having trouble to see why. If I apply a explore
on any node of the following graph, the first finished node will be one of inside a sink strongly connected component.
Wikipedia's description of the algorithm seems to confirm this. The first DFS prepends instead of appending.
Can someone show an example (if any) where using the reversed topological order of the original graph instead of the topological order of the transposed graph is wrong?