psionic_08's blog

Cses graph section doubt
By psionic_08, history, 4 months 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

»
4 months ago, # |
  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
  • »
    »
    4 months ago, # ^ |
      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
    • »
      »
      »
      4 months ago, # ^ |
      ← 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
»
4 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

To solve the problem, you just need to look for any cycle in the graph. To do this, you can perform a dfs and keep track of the tree it generates using an array of parents, where $$$parent[v] = u$$$ if $$$v$$$ is a direct descendant of $$$u$$$, and for the root node, you can set $$$parent[root] = -1$$$.

Suppose we are at node $$$u$$$, and let $$$v$$$ be a direct child of $$$u$$$. Then there exists a cycle if $$$v$$$ has a $$$backedge$$$ with an ancestor node of $$$u$$$ in the DFS tree, or if $$$v$$$ has a descendant node that has a $$$backedge$$$ with an ancestor node of $$$u$$$.

Let $$$v$$$ be the node with a $$$backedge$$$ to $$$w$$$ ancestor of $$$u$$$. Therefore, we can traverse in reverse order from $$$v$$$ to $$$w$$$ using the parent array and construct an array $$$ans$$$ composed by $$$[w, ..., u, v,w]$$$, which would be our cycle.

Time Complexity: $$$O(n + m)$$$

My solution
→ Reply