I have a directed graph (with possible selfloops 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 whitegreyblack visiting, but can't get it right. I am stuck from a long time. asked 13 Apr '18, 22:40
converted to question 13 Apr '18, 22:45

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/stronglyconnectedcomponents/tutorial/ answered 14 Apr '18, 01:39

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.