This question already has an answer here:

I saw this post, and it explains about why kosaraju's algorithm includes transpose graph $G^T$.

But, I totally didn't understand why cannot use increasing order of original graph. Kosaraju's algorithm uses decreasing order of transpose graph.

Is there an any counter example about this? I'm really confusing.


marked as duplicate by Apass.Jack, Evil, David Richerby, Yuval Filmus, Discrete lizard Feb 8 at 18:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 1. Something is wrong with your link. 2. Have you tried to construct a counterexample? Try enumerating a bunch of graphs with 3 or 4 or 5 vertices. $\endgroup$ – D.W. May 23 '18 at 15:32
  • $\begingroup$ I edited my link and I tried to find counterexample by drawing the graph, but I cannot find... $\endgroup$ – molamola May 23 '18 at 23:03
  • 1
    $\begingroup$ Check cs.stackexchange.com/q/47298/755, cs.stackexchange.com/q/60503/755, cs.stackexchange.com/q/48625/755. Do any of those help? $\endgroup$ – D.W. May 23 '18 at 23:09
  • $\begingroup$ Thank you for your answer, but I have an exam 2 hours later, so I will check later. $\endgroup$ – molamola May 23 '18 at 23:11
  • 3
    $\begingroup$ Possible duplicate of Kosaraju's Algorithm-Strongly connected components, which contains the same answer below by K. Ali and whose accepted answer contains a counterexample. $\endgroup$ – Apass.Jack Feb 8 at 8:06

Browse other questions tagged or ask your own question.