tgp07's blog

Cycles in a graph
By tgp07, history, 6 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

check this problem maybe help you 977E - Cyclic Components

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    Do you know how to go about getting the lengths of a cycle?

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

      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)

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

      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 explain

      Link

      → Reply