CODEWITHSUNDEEP
algorithmgraph
MAG
MAG

Reputation: 3075

How to detect cycle in a cycle in a Directed graph

I recently got a question in amazon interview and wanted to know stack overflow's views on the same .

Question is that

Input: A directed graph represented by adjacency list

Output required : does this graph have a cycle in a cycle and if yes what are those cycles . A cycle in a cycle condition is defined as follows : there are 2 cycles C1 and C2 in the graph & both of these share one or more edges then they will be called as cycles in a cycle .

Example bellow :
Cycle in a cycle

In the above graph one can see there are 2 cylces C->D->E->F->G->H->C and another cycle represented as H->I->J->G->H .. We can see that these 2 cycles have the edges G->H as a shared edge and hence we can call these as cycles in a cycle . 

So tha answer will be yes there are cycles in a cycles and
 the cyles are  C->D->E->F->G->H->C and H->I->J->G->H

My approach in an interview was to detect all cycles ( via DFS traversal ) and once detected maintain there edges in a hash map . Then when another cycle is found I again push them in hash . This was politely rejected and he moved further in the interview without discussing further . I then figured that finding all cycles is a hard problem . I am confused . Can someone please clarify .

Upvotes: 4

Views: 849

Answers (1)

MrSmith42
MrSmith42

Reputation: 10161

  1. Find all cycles
  2. Check for nonempty intersections between the edges of each pair of cycles (If the intersection is not empty the two cycles are a cycle in a cycle)

Upvotes: 1

Related Questions