All Paths from Source Lead to Destination
The 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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland

Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India

Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question