Tarjan's Algorithm can be used to find strongly connected sets of nodes in linear time. Each strongly connected component contains one or more cycles. But there could be a lot of them, so enumerating them will not be O(N) if N is the number of nodes.
On Jan 16, 12:40 pm, marti <[email protected]> wrote: > Okay,in the best complexity, whats your method?? > > > > > > > > On Wednesday, January 16, 2013 8:57:46 PM UTC+5:30, Don wrote: > > > The length of the cycles could be related to N, and the number of the > > cycles could be exponentially related to N, so printing them in linear > > time is not possible, even if you could detect them. > > Don > > > On Jan 16, 12:00 am, marti <[email protected]> wrote: > > > Detect and *print *all the cycles present in a Directed Graph in linear > > > time. --
