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) }