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

×

# Help in DFS code

 0 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 5★rahul_g 118●4 accept rate: 14% 15.2k●1●18●61 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)

 0 Find Strongly Connected Components and try to solve the problem on the condensed graph. You can read more about finding SCCs here : https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/ answered 14 Apr '18, 01:39 1.4k●11 accept rate: 28%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,701
×1,197
×1,056
×710

question asked: 13 Apr '18, 22:40

question was seen: 199 times

last updated: 14 Apr '18, 09:50