You are not logged in. Please login at www.codechef.com 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, 22:40

rahul_g's gravatar image

1★rahul_g
1
accept rate: 0%

converted to question 13 Apr, 22:45

vijju123's gravatar image

4★vijju123 ♦
12.6k1425

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, 09:50) vishesh_3454★

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/

link

answered 14 Apr, 01:39

hemanth_1's gravatar image

6★hemanth_1
1.3k9
accept rate: 25%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,221
×1,050
×923
×560

question asked: 13 Apr, 22:40

question was seen: 81 times

last updated: 14 Apr, 09:50