The DirectedCycleX class represents a data type for determining whether a digraph has a directed cycle. The HasCycle operation determines whether the digraph has a directed cycle and, and of so, the Cycle operation returns one.

This implementation uses a nonrecursive, queue-based algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasCycle operation takes constant time; the Cycle operation takes time proportional to the length of the cycle.

See for a recursive version that uses depth-first search. See or to compute a topological order when the digraph is acyclic.