# Longest path in directed graph cyclic graph where each node has one children

Consider given directed unweighted cyclic graph with $N$ nodes, and $N$ edges, and each node has at most one out-going children. Find the longest path.

Example

Consider the following graph, the path $2, 3, 1$ is the longest covering all 3 nodes.

What I think for the solution

Because every node has at most one children we form some type of equation that for node $a$, and it's children $b$, the path starting from node $a$ = path to start from $b + 1$, but I think because there are cycles this wont work.

• What do you mean by 'longest path'? If the graph has cycles, there is no longer path -- for any path you have in mind, I can find one that is even longer (by traversing the cycle as many times as needed until my path is longer than yours). Did you mean the longest simple path? – D.W. Jan 22 '18 at 18:34

As rus9384 & 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.