797.All Paths From Source to Target
===

###### tags: `Medium`,`Backtracking`,`Depth-First Search`,`Breadth-First Search`,`Graph`

[797. All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/description/)

### 題目描述

Given a directed acyclic graph (**DAG**) of `n` nodes labeled from `0` to `n - 1`, find all possible paths from node `0` to node `n - 1` and return them in **any order**.

The graph is given as follows: `graph[i]` is a list of all nodes you can visit from node i (i.e., there is a directed edge from node `i` to node `graph[i][j]`).

### 範例

**Example 1:**


Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

**Example 2:**


Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

**Constraints**:

* `n == graph.length`
* `2 <= n <= 15`
* `0 <= graph[i][j] < n`
* `graph[i][j] != i` (i.e., there will be no self-loops).
* All the elements of `graph[i]` are **unique.**
* The input graph is **guaranteed** to be a **DAG.**

### 解答
#### Python

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        DAG = defaultdict(list)
        paths = []

        for u, node in enumerate(graph):
            for v in node:
                DAG[u].append(v)

        def dfs(u, path):
            if u == len(graph) - 1:
                paths.append(path.copy())
                return

            for v in DAG[u]:
                path.append(v)
                dfs(v, path)
                path.pop()
                
        dfs(0, [0])
        return paths

> [name=Kobe][time=Fri, Dec 30, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)