LeetCode 797. 所有可能的路径

题目描述

给你一个有 $n$ 个节点的 有向无环图（DAG），请你找出所有从节点 $0$ 到节点 $n-1$ 的路径并输出（不要求按特定顺序）

二维数组的第 $i$ 个数组中的单元都表示有向图中 $i$ 号节点所能到达的下一些节点，空就是没有下一个结点了。

译者注：有向图是有方向的，即规定了 $a→b$ 你就不能从 $b→a$ 。

数据范围

n == graph.length
$2 \le n \le 15$
$0 \le graph[i][j] < n$
$graph[i][j] \not= i$ （即，不存在自环）
graph[i] 中的所有元素 互不相同
保证输入为 有向无环图（DAG）

样例

输入样例1：

graph = [[1,2],[3],[3],[]]

输出样例1：

[[0,1,3],[0,2,3]]

样例1解释：

有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

输入样例2：

graph = [[4,3,1],[3,2,4],[3],[4],[]]

输出样例2：

[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

样例2解释：

输入样例3：

graph = [[1],[]]

输出样例3：

[[0,1]]

输入样例4：

graph = [[1,2,3],[2],[3],[]]

输出样例4：

[[0,1,2,3],[0,2,3],[0,3]]

输入样例5：

graph = [[1,3],[2],[3],[]]

输出样例5：

[[0,1,2,3],[0,3]]

思路

从 $0$ 开始，沿着路径进行dfs。

在递归的时候：

假设当前节点为： $u$ ，首先将当前点加入到当前路径中。
如果当前节点为 $n - 1$ ，则将当前路径添加到答案数组中。
每次取出 $u$ 可到达的点 $x$ ，递归到下一个点 $x$ 。

这个图是 有向无环图 ，搜索过程中不会重复遍历一个点，所以不需要开一个数组标记这个点是否被访问过了。

代码

C++

class Solution {
    vector<vector<int>> res;
    vector<int> path;
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        dfs(graph, 0);
        return res;
    }

    void dfs(vector<vector<int>> &g, int u)
    {
        path.push_back(u);
        if ( u == g.size() - 1 ) res.push_back(path);
        for ( auto x : g[u] ) dfs(g, x);
        path.pop_back();
    }
};

Java

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        dfs(graph, 0);
        return res;
    }

    void dfs(int g[][], int u)
    {
        path.offerLast(u);
        if ( u == g.length - 1 ) res.add(new ArrayList<Integer>(path));
        for ( int x : g[u] ) dfs(g, x);
        path.pollLast();
    }
}