Minimum number of vertices to reach all nodes

Graph Theory

81.5% acceptance

Feb 25, 2026

3862

135

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi. Find the smallest set of vertices from which all nodes in the graph are reachable.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_smallest_set_of_vertices(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
    // Nodes with no incoming edges cannot be reached from any other node
    let mut has_incoming = vec![false; n as usize];
    for e in &edges {
      has_incoming[e[1] as usize] = true;
    }
    (0..n).filter(|&i| !has_incoming[i as usize]).collect()
  }
}