797-所有可能的路径

LeetCode 797. 所有可能的路径

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

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

method: 回溯

vector<vector<int>> res;
vector<int> path;
void dfs(vector<vector<int>>& graph, int index, int end) {
    path.push_back(index);
    if (index == end) {
        res.push_back(path);    // 注意这里不能return，不然最后一个节点没有pop
    }
    for (int i = 0; i < graph[index].size(); i++) {
        int v = graph[index][i];
        dfs(graph, v, end);
    }
    path.pop_back();
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    int n = graph.size();
    dfs(graph, 0, n - 1);
    return res;
}

另一种写法是把path的修改放在循环中，这样要先把第一个节点放进来

vector<vector<int>> res;
vector<int> path;
void dfs(vector<vector<int>>& graph, int index, int end) {
    if (index == end) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < graph[index].size(); i++) {
        int v = graph[index][i];
        path.push_back(v);
        dfs(graph, v, end);
        path.pop_back();
    }
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    int n = graph.size();
    path.push_back(0);
    dfs(graph, 0, n - 1);
    return res;
}