797. All Paths From Source to Target

川长思鸟来 2022-05-24 13:42 194阅读 0赞

/\*  
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.  
  
Example:  
Input: \[\[1,2\], \[3\], \[3\], \[\]\]  
Output: \[\[0,1,3\],\[0,2,3\]\]  
Explanation: The graph looks like this:  
0--->1  
|    |  
v    v  
2--->3  
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.  
  
Note:  
  
    The number of nodes in the graph will be in the range \[2, 15\].  
    You can print different paths in any order, but you should keep the order of nodes inside one path.  
  
  
  
\*/  
  
class Solution \{  
    public List<Integer> column;  
      
    public List<List<Integer>> allPathsSourceTarget(int\[\]\[\] graph) \{  
        List<List<Integer>> g = new ArrayList<List<Integer>>();  
        List<Integer> path = new ArrayList<Integer>();  
        path.add(0);  
        DFS(graph,0,g,path);  
        return g;  
    \}  
      
    public void DFS(int\[\]\[\] graph, Integer node, List<List<Integer>> g, List<Integer> path)\{  
        if(node==graph.length-1)\{  
            g.add(new ArrayList<Integer>(path));  
            return;  
        \}  
          
        for(int nextNode:graph\[node\])\{  
            path.add(nextNode);  
            DFS(graph, nextNode, g, path);  
            path.remove(path.size()-1);  
        \}  
    \}  
\}