wallcrawler's blog

By wallcrawler, history, 3 months ago, In English,

As given in cp-algorithms.com for SCC, that we need to reverse the graph after sorting the vertices in decreasing order of exit time for finding strongly connected component so that we do not jump out into another SCC.

But instead of reversing the graph and traversing it can't we just traverse the original graph with increasing order of exit time ??

Please Help!! Thanks in advanced :)

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No. Consider this case.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much, I was struggling for a while now, my thing reports just 1 !! :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it