Graph in C++

797. All Paths From Source to Target

All Paths From Source to Target - LeetCode

Naive implementation

Run time 88 ms

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<pair<int, vector<int>>> open_list={{0,{0}}};
        vector<vector<int>> paths;
        const int n=graph.size();
        if(n==0)return {};
        if(n==1)return {{0}};
        while(!open_list.empty()){
            auto node = open_list.back();
            open_list.pop_back();
            if( node.first==n-1)paths.push_back(node.second);
            for(auto&j:graph[node.first]){
                vector<int> this_path = node.second;
                this_path.push_back(j);
                open_list.emplace_back(j, this_path);
            }
        }
        return paths;
    }
};

More concise from lee215 by using backtrack

runtime is almost the same which is 76ms.

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