Enumerate All Simple Directed Cycles

Given a directed graph as an adjacency list, return every distinct simple directed cycle.

For this practice version, a simple directed cycle follows directed edges back to its starting vertex without repeating any other vertex. Represent a cycle as an array of its vertices without repeating the starting vertex at the end. The last vertex must have an edge to the first. A self-loop is a one-vertex cycle.

Input

• graph: an array of adjacency lists. Vertices are labeled 0 through graph.length - 1; graph[u] lists the vertices reachable by one directed edge from u.

Output

Return the cycles in canonical form:

• Rotate each cycle so its smallest vertex label appears first.
• List each such cycle once. Rotations of a sequence represent the same cycle.
• Preserve edge direction. Reversing a sequence does not generally represent the same directed cycle.
• Sort the resulting arrays lexicographically by their vertex sequences, using the shorter sequence first when one is a prefix of another.

Constraints and Edge Cases

• For this practice version, 1 <= graph.length <= 8.
• Adjacency lists may be unsorted but contain no repeated neighbors.
• The graph may be disconnected and may contain self-loops.
• If the graph contains no directed cycles, return an empty array.

Example 1

graph = [[1], [2], [0,1], []]
output = [[0,1,2], [1,2]]

The cycles [1,2,0] and [2,0,1] are rotations of [0,1,2], so they are not additional results.

Example 2

graph = [[0,1,2], [0,2], [0,1]]
output = [[0], [0,1], [0,1,2], [0,2], [0,2,1], [1,2]]

Both [0,1,2] and [0,2,1] are valid because their directed edges exist, and they are distinct. The self-loop contributes [0].

Enumerate All Simple Directed Cycles

Approach

Choose each vertex in turn as the minimum vertex of a possible cycle. Starting there, use depth-first search to extend a path along directed edges. Track which vertices are on that path. An edge back to the start completes a cycle, so append a copy of the path without repeating its first vertex. Otherwise extend only to an unused vertex whose label is greater than the chosen start. Undo the path and membership changes when returning from a recursive call.

Every emitted sequence follows existing directed edges and closes back to its start. Path membership prevents repeated internal vertices, and the label restriction makes the start its smallest vertex. A self-loop is recognized immediately and produces the singleton path. For any simple cycle, choose its smallest label as the start. All remaining cycle vertices have larger labels, so following that cycle's edges is an allowed search branch and eventually emits it. No other starting label can emit a rotation of it. Since each adjacency list contains no duplicate neighbor, the same path sequence cannot be generated twice. Reversals remain separate when their directed edges exist, and two-vertex cycles are naturally emitted once.

Sort the collected arrays by numeric lexicographic order, comparing labels until the first difference and putting a shorter proper prefix first. This makes the result independent of adjacency-list order. It also places a self-loop before longer cycles with the same starting vertex.

Let P be the number of simple path prefixes explored and C the number of cycles returned. Each prefix examines at most n outgoing edges, each stored cycle has at most n labels, and sorting uses O(nClog(C+1)) comparison work. The total time is O(nP + nClog(C+1)); factorial growth is inherent in the possible number of cycles. The recursion and path state use O(n) space, while results and sorting storage fit within O(nC + n). Depth is at most n <= 8.

For the full eight-vertex domain, a complete directed graph with loops maximizes both possible prefix paths and cycles. For a chosen minimum with m larger vertices, there are sum over j=0..m of m!/(m-j)! paths. Across m=0..7, these counts total 1+2+5+16+65+326+1957+13700 = 16072. In the complete graph each such path closes, so this is also the maximum cycle count. Equivalently, cycles of length l number choose(8,l)*(l-1)!. These bounds cover the full n <= 8 domain without truncating results.

• Time complexity: O(nP + nC*log(C+1)), where P is the number of explored simple path prefixes and C the output cycle count; n <= 8.
• Space complexity: O(n) search state, plus O(n*C) returned cycles and sorting storage.