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?
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 :)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With