0
$\begingroup$

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.

Example

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Jan 22, 2018 at 18:34

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.