Answers to: Can anyone suggest me how can i find longest chain of nodes ?https://discuss.codechef.com/questions/67790/can-anyone-suggest-me-how-can-i-find-longest-chain-of-nodes<p>Can anyone suggest me how can i find longest chain of nodes in unweighted acyclic graph .It is also given that u can choose any node as a first node. </p>enTue, 30 Jun 2015 01:54:51 +0530Answer by retrogradhttps://discuss.codechef.com/questions/67790/can-anyone-suggest-me-how-can-i-find-longest-chain-of-nodes/72476<p>If the graph is a DAG, then the first idea that would come into my head is a DP with memoization: </p>
<p>DP[v] -> the longest chain starting from vertex v. </p>
<p>Then DP[v] = 1+max{DP[w], w in Adj(v)}.
You can easily compute this with memoization</p>
<p>Your answer is then max{DP[v]} for each vertex</p>
<p>If the graph is undirected, then it is a forest of trees, and this is a whole different problem (diameter of a tree)</p>retrogradTue, 30 Jun 2015 01:54:51 +0530https://discuss.codechef.com/questions/67790/can-anyone-suggest-me-how-can-i-find-longest-chain-of-nodes/72476