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.

  • $\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$ – John L. Feb 8 '19 at 8:06

Browse other questions tagged or ask your own question.