All paths from source lead to destination

Graph Theory Topological Sort

37.0% acceptance

Mar 31, 2026

765

433

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn leads_to_destination(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
    let n = n as usize;
    let mut graph = vec![vec![]; n];
    for e in &edges {
      graph[e[0] as usize].push(e[1] as usize);
    }
    let dest = destination as usize;
    // Destination must have no outgoing edges (otherwise path can continue past it)
    if !graph[dest].is_empty() {
      return false;
    }
    // 0=unvisited, 1=in-stack, 2=done
    let mut color = vec![0u8; n];
    Self::dfs(&graph, source as usize, dest, &mut color)
  }

  fn dfs(graph: &Vec<Vec<usize>>, node: usize, dest: usize, color: &mut Vec<u8>) -> bool {
    if color[node] == 1 { return false; } // cycle
    if color[node] == 2 { return true; }  // already verified
    if graph[node].is_empty() {
      return node == dest;
    }
    color[node] = 1;
    for &next in &graph[node] {
      if !Self::dfs(graph, next, dest, color) {
        return false;
      }
    }
    color[node] = 2;
    true
  }
}