You are not logged in. Please login at to post your questions!


Help in DFS code

I have a directed graph (with possible self-loops and cycles). Each vertex has a certain value. Given the graph, I need to find the maximum value that is reachable from each vertex. I have tried applying dfs but I am stuck at the condition when a cycle occurs. I have also tried approaching it with white-grey-black visiting, but can't get it right. I am stuck from a long time.
Please help. ll dfs(ll s) { if (vis[s]==2) return rch[s]; vis[s] = 1; ll m = val[s]; for (ll x: adj[s]) { if (vis[x]==1) continue; m = max(m, dfs(x)); } vis[s] = 2; rch[s] = m; return m; }

asked 13 Apr '18, 22:40

rahul_g's gravatar image

accept rate: 14%

converted to question 13 Apr '18, 22:45

vijju123's gravatar image

4★vijju123 ♦♦

In DFS condition of cycle occurs when a node say A is in the adjacency list of node B and A is not the parent of B whose adjacency list is being checked. So if such node (i.e not parent) is already visited by some other node then there is a cycle but you are not handling that case. if(vis[x]==1) then also update the value of m by m = max (m,rch[x]). I guess your code finds the current maximum for any node only for the tree edges. It should do the same for back edges.

(14 Apr '18, 09:50) vishesh_3451★

Find Strongly Connected Components and try to solve the problem on the condensed graph. You can read more about finding SCCs here :


answered 14 Apr '18, 01:39

hemanth_1's gravatar image

accept rate: 28%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 13 Apr '18, 22:40

question was seen: 199 times

last updated: 14 Apr '18, 09:50