Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using Strongly Connected Components Algo as Cycle Detection

I understand that if a set of vertices are part of strongly connected components, then all those vertices within the component can reach one another; a cycle.

Now, I would like to use this fact and claim that if a graph G = (V,E) has a cycle, then that cycle MUST BE inside scc.

In other words, all cycles must be part of scc (my claim).

I cant think of any counterexample to my claim, so I would like to know if there are any cycles in a graph that are not part of scc.
Or Is my claim, correct?

like image 204
antz Avatar asked Oct 18 '12 16:10

antz


1 Answers

It's correct. If a set of vertices are in a cycle, then they are all reachable from each other (by going around the cycle), so they are an SCC by definition.

Having said that, it's not exactly a programming problem :)

like image 192
rici Avatar answered Oct 01 '22 23:10

rici