Force deduction DFS

Here you are  n  Of nodes Directed acyclic graph （DAG）, Please find all slave nodes 0  To the node n-1  And output （ No specific order is required ）

 graph[i]  Is a slave node i List of all nodes that can be accessed （ That is, the slave node i To the node  graph[i][j] There is a directed side ）.

Example 1：

Input ：graph = [[1,2],[3],[3],[]]
Output ：[[0,1,3],[0,2,3]]
explain ： There are two paths 0 -> 1 -> 3 and 0 -> 2 -> 3
Example 2：

Input ：graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output ：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
 

Tips ：

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i（ That is, there is no self ring ）
graph[i] All elements in Different from each other
Ensure that the input is Directed acyclic graph （DAG）

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/all-paths-from-source-to-target
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

class Solution {
    // Create a two-dimensional list 
    List<List<Integer>> ret = new LinkedList<>();
    // Create a stack , use Deque Class to achieve 
    Deque<Integer> stack = new ArrayDeque<>();
    
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        stack.offerLast(0); // You have to use offerLast Oh , Otherwise, the result will be the opposite , You can try 
        dfs(graph, 0, graph.length-1);
        return ret;
    }

    //dfs Depth first search traversal 
    public void dfs(int[][] graph, int start, int end){
        if(start==end){
            ret.add(new ArrayList<Integer>(stack));//stack What is it? , I will use it. stack To construct a ArrayList() object , Put every element in ArrayList Inside 
            return;
        }

        for(int x : graph[start]){
            stack.offerLast(x);
            dfs(graph, x, end);
            stack.pollLast();
        }
    }
    
}