### tgp07's blog

By tgp07, history, 7 weeks ago,

Let's you have a graph with n nodes and m bi-directional edges. (n, m <= 1e5). How would I get the cycles in this graph in an efficient way using DFS.

BTW, I've linked an image where I drew what I thought is a cycle. If it's not a cycle, please tell me what a cycle actually is.

https://imgur.com/a/Qrrg8DF

• -4

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 I can't open your link. I'm not sure what you mean 'cycle'. But actually for a graph, there can be 2 ^ v cycles.
 » 7 weeks ago, # |   0 check this problem maybe help you 977E - Cyclic Components
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 A graph contains a cycle if during a graph traversal, we find a node whose neighbor (other than the previous node in the current path) has already been visited.
•  » » 7 weeks ago, # ^ |   0 Do you know how to go about getting the lengths of a cycle?
•  » » » 7 weeks ago, # ^ |   0 The length of the cycle is the difference in heights of those two nodes on the DFS tree, plus one (for the edge going back up the DFS tree)
•  » » » » 7 weeks ago, # ^ |   0 Thanks, this makes sense.
•  » » » 7 weeks ago, # ^ |   0 There is a problem called 'Round Trip' in cses ,I just solved that and learnt clearly how to find and print the length of cycle and cycle itself,I can share my code ,if you still don't understand what I did just tell me then I will explainLink