All Paths From Source to Target
Given a DAG with nodes 0 to n-1, find all paths from node 0 to node n-1.
Input: adjacency list, one line per node (comma-separated neighbors, or 'none'). Output: one path per line.
Example
Input
1,2 3 3 none
Output
0 1 3 0 2 3
Reasoning
- The input represents a Directed Acyclic Graph (DAG) as an adjacency list, where each line corresponds to a node and its neighbors.
- The given input translates to the following graph structure: node 0 has neighbors 1 and 2, node 1 has a neighbor 3, node 2 has a neighbor 3, and node 3 has no neighbors.
- We perform a depth-first search (DFS) or similar traversal from node 0 to find all possible paths to node 3, which is the last node (n-1).
- The DFS yields two paths: 0 1 3 and 0 2 3, corresponding to the output lines.
- The final output lists each path on a separate line, resulting in
0 1 3and0 2 3.
Constraints
- 2 <= n <= 15
- 0 <= edges <= n * (n-1) / 2