Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/1059.html

 1059. All Paths from Source Lead to Destination

 Given the edges of a directed graph, and two nodes source and destination of this graph,
 determine whether or not all paths starting from source eventually end at destination, that is:

 At least one path exists from the source node to the destination node
 If a path exists from the source node to a node with no outgoing edges, then that node is equal to destination.
 The number of possible paths from source to destination is a finite number.
 Return true if and only if all roads from source lead to destination.


 Example 1:

 Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
 Output: false
 Explanation: It is possible to reach and get stuck on both node 1 and node 2.


 Example 2:

 Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
 Output: false
 Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.


 Example 3:

 Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
 Output: true


 Example 4:

 Input: n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2
 Output: false
 Explanation: All paths from the source node end at the destination node, but there are an infinite number of paths, such as 0-1-2, 0-1-1-2, 0-1-1-1-2, 0-1-1-1-1-2, and so on.
 Example 5:



 Input: n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1
 Output: false
 Explanation: There is infinite self-loop at destination node.


 Note:
     The given graph may have self loops and parallel edges.
     The number of nodes n in the graph is between 1 and 10000
     The number of edges in the graph is between 0 and 10000
     0 <= edges.length <= 10000
     edges[i].length == 2
     0 <= source <= n - 1
     0 <= destination <= n - 1

Algorithm

There are 2 cases it should return false.

  • case 1: it encounters a node that has no outgoing edges, but it is not destination.
  • case 2: it has cycle.

Otherwise, it returns true.

Could iterate graph with BFS. When indegree of a node becomes negative, then ther is cycle.

Time Complexity: O(n+e)

  • e = edges.length.

Space: O(n+e).

Code

  • public class All_Paths_from_Source_Lead_to_Destination {
    
        class Solution_bfs {
            public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
                Set<Integer>[] graph = new Set[n]; // node => set of its next nodes
    
                for (int i = 0; i < n; i++) {
                    graph[i] = new HashSet<Integer>();
                }
    
                int[] inDegrees = new int[n];
                for (int[] edge : edges) {
                    graph[edge[0]].add(edge[1]);
                    inDegrees[edge[1]]++;
                }
    
                LinkedList<Integer> q = new LinkedList<Integer>();
                q.add(source);
    
                while (!q.isEmpty()) {
                    int cur = q.poll();
                    if (graph[cur].size() == 0 && cur != destination) {
                        return false;
                    }
    
                    for (int nei : graph[cur]) {
                        if (inDegrees[nei] < 0) { // i.e. a cycle
                            return false;
                        }
    
                        inDegrees[nei]--;
    
                        q.add(nei);
                    }
                }
    
                return true;
            }
        }
    
        class Solution_dfs {
            public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
                Map<Integer, Set<Integer>> graph = new HashMap<>();
                for (int[] edge : edges) {
                    Set<Integer> neighbours = graph.getOrDefault(edge[0], new HashSet<>());
                    neighbours.add(edge[1]);
                    graph.put(edge[0], neighbours);
                }
                if (graph.get(destination) != null) return false;
                boolean[] isVisited = new boolean[n];
                isVisited[source] = true;
                return dfs(graph, isVisited, source, destination);
            }
    
            private boolean dfs(Map<Integer, Set<Integer>> graph, boolean[] isVisited, int source, int destination) {
                if (source == destination) {
                    return true;
                }
    
                Set<Integer> neighbours = graph.getOrDefault(source, new HashSet<>());
                if (neighbours.size() == 0) return false;
                for (int neib : neighbours) {
    
                    if (isVisited[neib]) return false; // cycle spotted
    
                    isVisited[neib] = true;
                    if (!dfs(graph, isVisited, neib, destination)) return false;
                    isVisited[neib] = false;
                }
                return true;
            }
        }
    }
    
    
    ############
    
    class Solution {
        private List<Integer>[] g;
        private int[] f;
        private boolean[] vis;
        private int k;
    
        public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
            vis = new boolean[n];
            g = new List[n];
            k = destination;
            f = new int[n];
            Arrays.setAll(g, key -> new ArrayList<>());
            for (var e : edges) {
                g[e[0]].add(e[1]);
            }
            return dfs(source);
        }
    
        private boolean dfs(int i) {
            if (i == k) {
                return g[i].isEmpty();
            }
            if (f[i] != 0) {
                return f[i] == 1;
            }
            if (vis[i] || g[i].isEmpty()) {
                return false;
            }
            vis[i] = true;
            for (int j : g[i]) {
                if (!dfs(j)) {
                    f[i] = -1;
                    return false;
                }
            }
            f[i] = 1;
            return true;
        }
    }
    
  • // OJ: https://leetcode.com/problems/all-paths-from-source-lead-to-destination/
    // Time: O(V + E)
    // Space: O(V + E)
    class Solution {
        vector<unordered_set<int>> G;
        vector<int> state; // -1 unvisited, 0 visiting, 1 visited
        int dest;
        bool dfs(int u) {
            if (state[u] != -1) return state[u];
            if (G[u].empty()) {
                return u == dest;
            }
            state[u] = 0;
            for (int v : G[u]) {
                if (!dfs(v)) return false;
            }
            return state[u] = 1;
        }
    public:
        bool leadsToDestination(int n, vector<vector<int>>& E, int source, int dest) {
            G.assign(n, {});
            state.assign(n, -1);
            this->dest = dest;
            for (auto &e : E) {
                G[e[0]].insert(e[1]);
            }
            return dfs(source);
        }
    };
    
  • class Solution:
        def leadsToDestination(
            self, n: int, edges: List[List[int]], source: int, destination: int
        ) -> bool:
            @cache
            def dfs(i):
                if i == destination:
                    return not g[i]
                if i in vis or not g[i]: # not g[i]: not destination but no more neigbours
                    return False
                vis.add(i)
                for j in g[i]:
                    if not dfs(j):
                        return False
                return True
    
            g = defaultdict(list)
            for a, b in edges:
                g[a].append(b)
            vis = set()
            return dfs(source)
    
    
    
  • func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
    	vis := make([]bool, n)
    	g := make([][]int, n)
    	f := make([]int, n)
    	for _, e := range edges {
    		g[e[0]] = append(g[e[0]], e[1])
    	}
    	var dfs func(int) bool
    	dfs = func(i int) bool {
    		if i == destination {
    			return len(g[i]) == 0
    		}
    		if f[i] != 0 {
    			return f[i] == 1
    		}
    		if vis[i] || len(g[i]) == 0 {
    			return false
    		}
    		vis[i] = true
    		for _, j := range g[i] {
    			if !dfs(j) {
    				f[i] = -1
    				return false
    			}
    		}
    		f[i] = 1
    		return true
    	}
    	return dfs(source)
    }
    

All Problems

All Solutions