Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

 

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Constraints:

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (i.e., there will be no self-loops).
• The input graph is guaranteed to be a DAG.

//from huahua

 

• class Solution {
  public:
      vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
          vector<vector<int>> ans;
          vector<int> path(1,0); //定义长度为1，初始值为0的数组path
          dfs(graph,0,graph.size()-1,path,ans);
          return ans;
      }
  private:
      void dfs( vector<vector<int>>& graph,int cur,int dest,vector<int> &path,vector<vector<int>>& ans){
          if(cur==dest){
              ans.push_back(path);
              return;
          }
          for(int next:graph[cur]){
              path.push_back(next);
              dfs(graph,next,dest,path,ans);
              path.pop_back(); //删除path数组中最后一个元素
          }
      }
      
  };