797. 所有可能的路径（中等）

题目：

题目输入一幅有向无环图，这个图包含n个节点，标号为0, 1, 2,..., n - 1，请你计算所有从节点0到节点n - 1的路径。

输入的这个graph其实就是「邻接表」表示的一幅图，graph[i]存储这节点i的所有邻居节点。

比如输入graph = [[1,2],[3],[3],[]]，就代表下面这幅图：

0->1

|     |

2->3

算法应该返回[[0,1,3],[0,2,3]]，即0到3的所有路径。

 

思路：labuladong

递归遍历所有结点，遍历到该节点时，使用path记录结点，当退出结点时从path末尾退出。当遍历的结点s为图的末尾时，将path记录到结果中

 

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> path;
        traverse(graph,0,path);
        return ret;
    }
    void traverse(vector<vector<int>>& graph, int s, vector<int>& path){
        path.push_back(s);
        int n=graph.size();
        if(s==n-1){
            ret.push_back(path);
            path.pop_back();
            return;
        }
        for(int i=0;i<graph[s].size();++i){
            traverse(graph,graph[s][i],path);
        }
        path.pop_back();
    }
    vector<vector<int>> ret;
};