Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

aman_naughty's blog

By aman_naughty, history, 2 years ago, In English

I want help please don't down-vote.

I want to print the cycle in an undirected graph. I know how to detect cycle in an undirected graph but can't determine how to find the vertices involved in the cycle. Here is the code to find cycle.

code

Can someone please tell me how to modify this so that I can get the vertices in the cycle as well.

I have seen geeksforgeeks article on printing all cycles but I can't understand it. Is there some simpler approach ?

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello! To do that you can use stack. In DFS you can push visited vertex to stack, and if there is a cycle then all elements from the top of stack (until you reach the last vertex) belong to the cycle

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When you do dfs, you can consider vertices of 3 types; unvisited, visited but in the stack, or visited and finished (we called dfs on all their neighbors and returned already).

If your dfs detects a cycle, then all the cycle vertices are the type that's in the stack (they must have been visited, but they cannot be finished because you will find a cycle before finishing any vertex on it). So, one easy way to find the cycle is to maintain the stack along with a dfs (vector or stack, either global or passed by reference). When you find a visited neighbor, iterate from the back of the stack until you reach that visited node, and put all the vertices you iterated on in some vector, representing the cycle.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks this helped

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks Noam! For future reference: the iteration process in the stack after you find a visited neighbour is a parallel process to the main DFS.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is the code according to Noam's idea if anyone wants to see Implementation
    Btw what if the graph was something like a wheatstone bridge, how would one print all cycles since this code only prints two out of the three cycles in a wheatstone bridge

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Sorry. My answer is wrong as I got the wrong definition of a cycle.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In an undirected graph, all nodes in the same connected component are in a cycle.

    I'm not sure that's right. Consider an undirected graph that is a chain/linked list. They are all part of the same connected component, but how is there a cycle?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right. I kinda forgot the definition of a cycle — I had the notion of SCCs in my head when thinking of cycles. But cycles require us to find a repeating sequence of nodes. Thanks for correcting me.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this problem can define a cycle in an undirected graph for you.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any one go idea how to do it usign bfs in undirected graph?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Using BFS it is more writing work than a simple DFS but still you can do that. Just run the BFS over the nodes and when you find a backedge (an edge to already visited node) , you have found a cycle .

    For printing the cycle just find the LCA (lowest common ancestor) of the nodes connected by that backedge and travel parent to parent from both the nodes to the LCA. now just connect the parts in order to find the given cycle , still i would say it is a lot easier using DFS. (For making a bit simple , don't use Binary lifting for finding the LCA)