Enumerate Directed Paths and Cycles
Learn this problem
ByteDanceNEW GRADPHONE SCREENProblem statement
You are given a directed graph as an adjacency list and two distinct vertices, start and target. Enumerate:
- every simple directed path from
starttotarget; and - every simple directed cycle anywhere in the graph.
A simple path or cycle does not repeat a vertex. A self-loop is a one-vertex cycle. Cycles that differ only by rotation are the same; represent each cycle with its smallest vertex first. Reversing a cycle is not an equivalence because edge direction matters.
Return a String[][] with exactly two rows. Row 0 contains the paths and row 1 contains the cycles. Encode each vertex sequence by joining its decimal vertex IDs with commas, without spaces. Sort both rows by lexicographic order of their integer sequences, comparing the first unequal integer and then length when one sequence is a prefix.
Function
enumeratePathsAndCycles(adjacency: int[][], start: int, target: int) → String[][]Examples
Example 1
adjacency = [[1,2],[2,3],[0,3],[]]start = 0target = 3return = [["0,1,2,3","0,1,3","0,2,3"],["0,1,2","0,2"]]There are three simple paths from 0 to 3. The graph also contains the normalized cycles 0,1,2 and 0,2.
Example 2
adjacency = [[0,1],[2],[1],[]]start = 0target = 2return = [["0,1,2"],["0","1,2"]]The path is 0,1,2. The graph also contains the self-loop at 0 and the two-vertex directed cycle 1,2.
Example 3
adjacency = [[1],[],[3],[]]start = 0target = 3return = [[],[]]The target is unreachable from the start, and the graph contains no directed cycle, so both rows are empty.
Constraints
1 <= adjacency.length <= 12.- Every neighbor is a vertex ID in
[0, adjacency.length - 1]. - The graph contains at most 40 directed edges and no duplicate edge.
0 <= start, target < adjacency.lengthandstart != target.