Longest path in directed graph cyclic graph where each node has one children
As rus9384 &amp; you seemed to have figured out in the comments, there exists an $O(N)$ solution to the problem. 

First, apply the well known algorithm to find Strongly Connected Components in the graph in $O(N)$. Then, after collapsing all such components into single nodes, you can slightly modify the algorithm to find the Longest Path in a DAG to get your answer in $O(N)$ time.