The people asking for the definition of "nested" have a point. Do you mean "sharing a vertex" or "sharing an edge?" If you assume it's "vertex," and also that there are no edges with head and tail on same vertex (self-loops) then finding the SCCs with e.g. Tarjan is the way to go. Count the number of vertices and edges in each SCC and if you have more edges than vertices, you have sharing. The logic is simple. If cycles share N vertices (decreasing the total by N), they share only N-1 edges (decreasing by only N-1). For example above, in place of the 10 vertices and 10 edges it would take for the cycles to be disjoint (2 separate SCCs), you are sharing 2 vertices and 1 edge, so the totals are 8 and 9.
Gene On Aug 31, 11:16 am, MAC <macatad...@gmail.com> wrote: > Q The question asked in interview of a startup : suppose you have a graph > as shown bellow : please see the attachment . The red dots are graph > vertexes ( you can see 1 vertex alone , aloof ) > so you can see there are 2 cycles one inside another . How will you find > such a scenario in a graph i.e. a cycle within a cycle. > > When i couldn't answer he asked how will you find strongly conected > components of a graph (since it was follow up it MIGHT be related to > solution but thought its good to share ) > > any thoughts on these 2 questions > -- > thanks > --mac > > pb.GIF > 4KViewDownload -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
