Hi Everyone!

I haven't been active lately because of interviews going on. Recently I appeared for Amazon Interview for Internship and there was a problem that I still have doubts with:

As you can see the graph is not an unweighted DAG, Hence, the problem became finding acyclic longest chain in a directed cyclic graph.

I wasn't able to come with a clear solution (O(n)) because it didn't feel right that how I can take care of cases with a cycle using maybe topological sort? So I wanted to ask what is the best possible complexity answer for this.

Thanks!