Reversing topo-order of the original graph instead of the topo-order of the transposed graph?

Question

(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?

Answer 1

It may work for the graph you give, but not for all graphs. Consider a graph with 3 vertices, A, B, and C.

$A \rightarrow B, C$

$B \rightarrow A$

Search on A, exploring B before C, B finishes first but is not in a sink.

Also, note that for the Wikipedia article, the search is on incoming edges, not outgoing, which is why it doesn't need to explicitly transpose the graph.

Answer 2

My intuition for why the reverse topological order is necessary is that given a node $v$ in a strongly connected component $C$, if $v$'s finishing time (denoted in CLRS as $f(v)$) is maximal, than so is $C$'s. However, if $f(v)$ is minimal, $f(C)$ might not be minimal. In order for the algorithm to work without the transpose, at each stage you must be able to choose a node belonging to the SCC with the lowest remaining $f(C)$, which is generally not possible without already knowing what the SCCs of the graph are.

By the way, your question is identical to exercise 22.5-3 in CLRS version 3, and you can also find other answers to it online.