= Solution
An infinite trace exists \b[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 \b[$O(|V|+|E|)$], with $O(|V|+|E|)$ auxiliary space for a straightforward transpose-based implementation.
Back to article page
