[leetcode]797. All Paths From Source to Target

Analysis

周四不知道快不快乐—— [有点想回家过暑假的冲动！]

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length – 1. graph[i] is a list of all nodes j for which the edge (i, j) exists

给定一张有向无环图，图中有n个点，返回节点0到节点n-1的所有路径。用DFS解决，然后注意要回溯~

Implement

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        n = graph.size();
        edge.resize(n);
        for(int i=0; i<n; i++){
            for(int j=0; j<graph[i].size(); j++){
                edge[i].push_back(graph[i][j]);
            }
        }
        vector<int> path;
        DFS(0, path);
        return res;
    }
    void DFS(int u, vector<int>& path){
        path.push_back(u);
        if(u == n-1){
            res.push_back(path);
            return ;
        }
        for(int i=0; i<edge[u].size(); i++){
            DFS(edge[u][i], path);
            path.pop_back();
        }
    }
private:
    vector<vector<int>> edge;
    int n;
    vector<vector<int>> res;
};