psionic_08's blog

Cses graph section doubt
By psionic_08, history, 3 years ago, In English

Can anyone help me out with this problem, I looked up on many places but couldn't find any satisfactory solution

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

Comments Comments (3)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

you can just simply search for cycle in undirected graph and keep a parent array if you find cycle just backtrack using parent array

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    tried that but it fails in the case my dfs starting point is in the cycle as it would have no parent

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      Once you reach an already visited node X which isn't the parent keep pushing parent-nodes into vector until you reach X Then terminate the dfs and print the ans

      → Reply