All Paths From Source to Target

给一个DAG(有向无圈图), 求从0到n-1的所有路径.

直接dfs

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> tmp; 
        dfs(graph, tmp, 0);
        return res;
    }
    void dfs(vector<vector<int>>& graph, vector<int>& tmp, int cur){
        tmp.push_back(cur);
        if(cur == graph.size() - 1){
            res.push_back(tmp);
            return;
        }
        for(auto i : graph[cur]){
            dfs(graph, tmp, i);
            tmp.pop_back();
        } 
    }
};