Longest Path - Dynamic Programming / Tree


can we have a detailed description of how adj variable transfer to directed acyclic graph?

It was very unclear what the structure of the input looked like. I would really appreciate there being at least one example input.

I think the parents variable should be named has_parents or something. Line 12 comment should be ‘mark every node that has a parent node’.

Poorly written solution with horrendous comments in Soln. @Grinch’s suggestion below is spot on, you’re not storing parent nodes. Rather marking nodes that HAVE a parent. spent 15 mins looking at line 24 (in java soln) thinking WTF is going on & how are you marking parents this way. Wouldn’t you need to calculate in degree of nodes & those with 0 would be parents. Then saw Grinch’s comments & it makes sense. You’re marking nodes that HAVE a parent.
Also, your example cases don’t do justice. This can easily be done with DFS on a tree. But catch in this problem is, you have a graph which can have multiple components. So maybe add that as an example to hint that.