Naive (All Maximal Non-Branching Paths in a Graph All Maximal Non-Branching Paths in a Graph)

Time Complexity

$O(m)$

Space Complexity

$O(n)$? words

(For each vertex, store whether that vertex is a 1-in-1-out vertex (all of these can be pre-computed at the same time in $O(m)$ time). Unclear if there's a better bound)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1940

Reference

http://rosalind.info/problems/ba3m/