All Paths from Source Lead to Destination
MicrosoftThe problem
Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, 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.
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.
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.
Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
- 1 <= n <= 104
- 0 <= edges.length <= 104
- edges.length == 2
- 0 <= ai, bi <= n - 1
- 0 <= source <= n - 1
- 0 <= destination <= n - 1
cpp
class Solution {
public:
bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
// Your code goes here
}
};java
class Solution {
public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
// Your code goes here
}
}python
class Solution(object):
def leadsToDestination(self, n, edges, source, destination):
"""
:type n: int
:type edges: List[List[int]]
:type source: int
:type destination: int
:rtype: bool
"""
# Your code goes herejavascript
/**
* @param {number} n
* @param {number[][]} edges
* @param {number} source
* @param {number} destination
* @return {boolean}
*/
var leadsToDestination = function(n, edges, source, destination) {
// Your code goes here
};csharp
using System.Collections.Generic;
public class Solution {
public bool LeadsToDestination(int n, int[][] edges, int source, int destination) {
// Your code goes here
}
}go
func leadsToDestination(n int, edges [][]int, source int, destination int) boolStuck? Show a way to structure it+
- 01Build directed adjacency lists.
- 02Require destination to have no outgoing edges.
- 03DFS with unvisited, visiting, and safe states.
- 04Reject any cycle reachable from source.
- 05Require every terminal reachable node to equal destination.
Reference answer
Then expect these follow-ups
How would an iterative DFS represent the visiting state?
Tests: follow-up reasoning
What changes if the question asks whether some path reaches destination?
Tests: constraint adaptation
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question