Welcome to Subscribe On Youtube

797. All Paths From Source to Target

Description

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.

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]]

 

Constraints:

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

Solutions

Since there is no ring in the graph, you can simply use DFS or BFS to traverse it.

  • class Solution {
        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            int n = graph.length;
            Queue<List<Integer>> queue = new ArrayDeque<>();
            queue.offer(Arrays.asList(0));
            List<List<Integer>> ans = new ArrayList<>();
            while (!queue.isEmpty()) {
                List<Integer> path = queue.poll();
                int u = path.get(path.size() - 1);
                if (u == n - 1) {
                    ans.add(path);
                    continue;
                }
                for (int v : graph[u]) {
                    List<Integer> next = new ArrayList<>(path);
                    next.add(v);
                    queue.offer(next);
                }
            }
            return ans;
        }
    }
    
    
  • class Solution {
    public:
        vector<vector<int>> graph;
        vector<vector<int>> ans;
    
        vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
            this->graph = graph;
            vector<int> path;
            path.push_back(0);
            dfs(0, path);
            return ans;
        }
    
        void dfs(int i, vector<int> path) {
            if (i == graph.size() - 1) {
                ans.push_back(path);
                return;
            }
            for (int j : graph[i]) {
                path.push_back(j);
                dfs(j, path);
                path.pop_back();
            }
        }
    };
    
  • class Solution:
        def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
            n = len(graph)
            q = deque([[0]])
            ans = []
            while q:
                path = q.popleft()
                u = path[-1]
                if u == n - 1:
                    ans.append(path)
                    continue
                for v in graph[u]:
                    q.append(path + [v])
            return ans
    
    
  • func allPathsSourceTarget(graph [][]int) [][]int {
    	var path []int
    	path = append(path, 0)
    	var ans [][]int
    
    	var dfs func(i int)
    	dfs = func(i int) {
    		if i == len(graph)-1 {
    			ans = append(ans, append([]int(nil), path...))
    			return
    		}
    		for _, j := range graph[i] {
    			path = append(path, j)
    			dfs(j)
    			path = path[:len(path)-1]
    		}
    	}
    
    	dfs(0)
    	return ans
    }
    
  • /**
     * @param {number[][]} graph
     * @return {number[][]}
     */
    var allPathsSourceTarget = function (graph) {
        const ans = [];
        const t = [0];
    
        const dfs = t => {
            const cur = t[t.length - 1];
            if (cur == graph.length - 1) {
                ans.push([...t]);
                return;
            }
            for (const v of graph[cur]) {
                t.push(v);
                dfs(t);
                t.pop();
            }
        };
    
        dfs(t);
        return ans;
    };
    
    
  • impl Solution {
        fn dfs(i: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, graph: &Vec<Vec<i32>>) {
            path.push(i as i32);
            if i == graph.len() - 1 {
                res.push(path.clone());
            }
            for j in graph[i].iter() {
                Self::dfs(*j as usize, path, res, graph);
            }
            path.pop();
        }
    
        pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
            let mut res = Vec::new();
            Self::dfs(0, &mut vec![], &mut res, &graph);
            res
        }
    }
    
    

All Problems

All Solutions