### natofp's blog

By natofp, history, 5 years ago,

Hi,

can anyone provide a good source, or method to find any cycle in directed graph? The answer should be the list of edges ( pairs of vertices). I did not manage to find anything satisfying enough.

• -1

| Write comment?
 » 5 years ago, # |   0 Use dfs to find cycle, when you find it, just traverse back and when you get to node that you visited last you print the cycle. For example if you do dfs and traverse order is 1 - 2 - 3 - 4 - 5 - 2, then you traverse from back and when you reach 2 for the second time you print the edges. This can be done with one additional array.
•  » » 5 years ago, # ^ |   0 I think it is not that simple, that algorithm works on an undirected graph but fails on directed graphs like 0-->1 | | v v 2-->3 The problem is that in your algorithm if you start at 0 then 3 will kinda look like a cycle, even though it's not.
 » 5 years ago, # |   0 The simplest way is just to use DFS from any node. Then during the DFS keep track of how deep in the DFS each node you've visited is (lets call it index), also using recursion keep track of the earliest (least deep) node you've seen or any of your predecessor have seen (lets call it low_link). The idea is that if the index and low_link coincide for any node then you've found a cycle, because one of your predecessors have seen you. If the index and low_link never coincide then none of the nodes you've visited are part of any cycle so remove them from the graph. This is the main idea behind Tarjan's strongly connected components algorithm which does quite a bit more than just finding a cycle.
 » 5 years ago, # | ← Rev. 2 →   +6 Use colors, for example, white, grey and black. void dfs(int v, int p){ color[v] = 1; // GREY for(int w : g[v]){ if(color[w] == 1){ // you found a cycle, it's easy to recover it now. } if(color[w] == 0) dfs(w, v); } color[v] = 2; // BLACK } And then just call it from any white node. for(int i = 0; i < n; i++) if(color[i] == 0) dfs(i, -1); // IF NODE IS WHITE, START NEW DFS For more information read the CLRS. Specifically, you are interested in knowing what tree edges, back edges, cross edges and forward edges are.
•  » » 5 years ago, # ^ |   +5 This code fails to find a cycle in a graph with two edges : 0-->1 , 1-->0
•  » » » 5 years ago, # ^ |   0 Correct, thank you, I think I fixed it now.
•  » » 5 years ago, # ^ |   0 for n = 4,m = 6 1->2 2->4 4->3 3->1 3->2 2->3 this alog gives only 2 cycles but we have 3
•  » » » 5 years ago, # ^ |   0 This is only to determine if a cycle exists, not to count them.
•  » » » » 5 years ago, # ^ |   0 is there any way to find it efficiently ??
 » 5 years ago, # |   +21 Wait...am I color blind or something? Is that a div 1 coder asking this question? Hmm...seems fishy.
•  » » 5 years ago, # ^ |   +3 Plus the fact that expert answered the question.
•  » » 5 years ago, # ^ |   +4 You don't really need to know many algorithms to reach 1900. If you look at his recent contests you'll see that he consistently and quickly solves non-technical problems.
 » 5 years ago, # |   +5 I like the idea of maintaining the "path" using some boolean arrayfor example, you might has vis[n] and then in_path[n] do check whether a) the node has been visited or b) whether the node is in your current pathif you hit something already in your path then you've hit a cycle. To actually get to cycle you want to keep a stack with the actual path.For example, we are at node u and we hit node v, which is already in path. Then we know u is in the path, and we look backwards in the stack until we hit v.
 » 5 years ago, # |   0 you can use something like topological sort. after doing top sort some nodes will remain. You can just do a dfs, eventually you will reach to your starting node.
 » 3 years ago, # |   0 This is a great video, explaining the exact concept.
 » 23 months ago, # |   0 International Grandmaster doesn't know such a basic stuff. Kinda sus
•  » » 23 months ago, # ^ |   -10 he was not igm when he asked that question, he was a purple like you :)