Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 6 / d

An infinite trace exists exactly when a directed cycle is reachable from $s$, by the infinite walk criterion in a finite directed graph. Compute the reachable set with depth-first search, compute its strongly connected components, and return true if any component has at least two vertices or contains a self-loop. A singleton without a self-loop does not qualify.

If the test succeeds, follow a path from $s$ to the cycle and traverse the cycle forever. Conversely, an infinite trace in a finite graph repeats a vertex, producing a reachable nonempty closed walk and hence a directed cycle. Reachability, component construction and the self-loop check all scan adjacency lists only a constant number of times. The worst-case time is $O(|V|+|E|)$, with $O(|V|+|E|)$ auxiliary space for a straightforward transpose-based implementation.