All Paths from Source Lead to Destination

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.

Examples

Example 1

graph LR;
A(0):::blue --> B(1) & C(2):::green

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 
classDef blue fill:#0000FF,stroke:#000,stroke-width:1px,color:#fff;

1
2
3


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

graph LR;
A(0):::blue --> B(1) & D(3):::green
B --- C(2)
C ---B 

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 
classDef blue fill:#0000FF,stroke:#000,stroke-width:1px,color:#fff;

1
2
3


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

graph LR;
A(0):::blue --> B(1) & C(2)
B --> D(3):::green
C --- D

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 
classDef blue fill:#0000FF,stroke:#000,stroke-width:1px,color:#fff;

1
2


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

Constraints

1 <= n <= 10^4
0 <= edges.length <= 10^4
edges.length == 2
0 <= ai, bi <= n - 1
0 <= source <= n - 1
0 <= destination <= n - 1
The given graph may have self-loops and parallel edges.

Solution

Method 1 – DFS with Cycle and Dead-End Detection

Intuition

We need to ensure that every path from source leads to destination and nowhere else, and that there are no cycles (which would allow infinite paths). If we ever reach a node with no outgoing edges that isn’t destination, or revisit a node in the current path (cycle), we return false.

Approach

Build an adjacency list from the edges.
Use DFS to traverse from source.
Track visited nodes in the current path to detect cycles.
If a node has no outgoing edges, check if it’s destination.
If a cycle is detected, or a dead-end node is not destination, return false.
Use memoization to avoid redundant work.
Return true if all paths from source end at destination.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
  bool leadsToDestination(int n, vector<vector<int>>& edges, int src, int dest) {
    vector<vector<int>> g(n);
    for (auto& e : edges) g[e[0]].push_back(e[1]);
    vector<int> vis(n, 0); // 0=unvisited, 1=visiting, 2=visited
    return dfs(g, vis, src, dest);
  }
  bool dfs(vector<vector<int>>& g, vector<int>& vis, int u, int dest) {
    if (g[u].empty()) return u == dest;
    if (vis[u] == 1) return false;
    if (vis[u] == 2) return true;
    vis[u] = 1;
    for (int v : g[u]) {
      if (!dfs(g, vis, v, dest)) return false;
    }
    vis[u] = 2;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func leadsToDestination(n int, edges [][]int, src int, dest int) bool {
  g := make([][]int, n)
  for _, e := range edges {
    g[e[0]] = append(g[e[0]], e[1])
  }
  vis := make([]int, n)
  var dfs func(u int) bool
  dfs = func(u int) bool {
    if len(g[u]) == 0 {
      return u == dest
    }
    if vis[u] == 1 {
      return false
    }
    if vis[u] == 2 {
      return true
    }
    vis[u] = 1
    for _, v := range g[u] {
      if !dfs(v) {
        return false
      }
    }
    vis[u] = 2
    return true
  }
  return dfs(src)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
  public boolean leadsToDestination(int n, int[][] edges, int src, int dest) {
    List<Integer>[] g = new List[n];
    for (int i = 0; i < n; ++i) g[i] = new ArrayList<>();
    for (int[] e : edges) g[e[0]].add(e[1]);
    int[] vis = new int[n];
    return dfs(g, vis, src, dest);
  }
  boolean dfs(List<Integer>[] g, int[] vis, int u, int dest) {
    if (g[u].isEmpty()) return u == dest;
    if (vis[u] == 1) return false;
    if (vis[u] == 2) return true;
    vis[u] = 1;
    for (int v : g[u]) {
      if (!dfs(g, vis, v, dest)) return false;
    }
    vis[u] = 2;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
  fun leadsToDestination(n: Int, edges: Array<IntArray>, src: Int, dest: Int): Boolean {
    val g = Array(n) { mutableListOf<Int>() }
    for (e in edges) g[e[0]].add(e[1])
    val vis = IntArray(n)
    fun dfs(u: Int): Boolean {
      if (g[u].isEmpty()) return u == dest
      if (vis[u] == 1) return false
      if (vis[u] == 2) return true
      vis[u] = 1
      for (v in g[u]) if (!dfs(v)) return false
      vis[u] = 2
      return true
    }
    return dfs(src)
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
  def leadsToDestination(self, n: int, edges: list[list[int]], src: int, dest: int) -> bool:
    g: list[list[int]] = [[] for _ in range(n)]
    for a, b in edges:
      g[a].append(b)
    vis: list[int] = [0] * n  # 0=unvisited, 1=visiting, 2=visited

    def dfs(u: int) -> bool:
      if not g[u]:
        return u == dest
      if vis[u] == 1:
        return False
      if vis[u] == 2:
        return True
      vis[u] = 1
      for v in g[u]:
        if not dfs(v):
          return False
      vis[u] = 2
      return True

    return dfs(src)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


impl Solution {
  pub fn leads_to_destination(n: i32, edges: Vec<Vec<i32>>, src: i32, dest: i32) -> bool {
    let n = n as usize;
    let mut g = vec![vec![]; n];
    for e in edges.iter() {
      g[e[0] as usize].push(e[1] as usize);
    }
    let mut vis = vec![0; n];
    fn dfs(g: &Vec<Vec<usize>>, vis: &mut Vec<u8>, u: usize, dest: usize) -> bool {
      if g[u].is_empty() { return u == dest; }
      if vis[u] == 1 { return false; }
      if vis[u] == 2 { return true; }
      vis[u] = 1;
      for &v in &g[u] {
        if !dfs(g, vis, v, dest) { return false; }
      }
      vis[u] = 2;
      true
    }
    dfs(&g, &mut vis, src as usize, dest as usize)
  }
}

Complexity

⏰ Time complexity: O(E + N) where E is the number of edges and N is the number of nodes (each node and edge is visited at most once).
🧺 Space complexity: O(N) for recursion stack and visited array.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – DFS with Cycle and Dead-End Detection#

Intuition#

Approach#

Code#

Complexity#