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.

Thanks in advance.

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 174 |

5 | tourist | 166 |

6 | McDic | 164 |

6 | Um_nik | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

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.

Thanks in advance.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2020 14:38:00 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

I think it is not that simple, that algorithm works on an undirected graph but fails on directed graphs like

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.

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.

Use colors, for example, white, grey and black.

And then just call it from any white node.

For more information read the CLRS. Specifically, you are interested in knowing what tree edges, back edges, cross edges and forward edges are.

This code fails to find a cycle in a graph with two edges : 0-->1 , 1-->0

Correct, thank you, I think I fixed it now.

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

This is only to determine if a cycle exists, not to count them.

is there any way to find it efficiently ??

Wait...am I color blind or something? Is that a div 1 coder asking this question? Hmm...seems fishy.

Plus the fact that expert answered the question.

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.

I like the idea of maintaining the "path" using some boolean array

for 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 path

if 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.

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.

Initially all element of stack are assigned zero. Stack switch ON the current root node that was in the recursive stack memory (still not finish the dfs call). so use extra stack array to monitor the current stack.