All ancestors of a node in a directed acyclic graph

Depth-First Search Breadth-First Search Graph Theory Topological Sort

62.1% acceptance

Feb 25, 2026

1750

You are given a positive integer n representing the number of nodes of a DAG (nodes 0 to n-1). You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes a unidirectional edge. Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order. A node u is an ancestor of v if u can reach v via edges.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    use std::collections::{BTreeSet, VecDeque};
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    let mut radj = vec![vec![]; n];
    let mut in_deg = vec![0usize; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      radj[v].push(u);
      in_deg[v] += 1;
    }
    // Topological sort (Kahn's)
    let mut queue: VecDeque<usize> = (0..n).filter(|&i| in_deg[i] == 0).collect();
    let mut topo = Vec::new();
    while let Some(u) = queue.pop_front() {
      topo.push(u);
      for &v in &adj[u] {
        in_deg[v] -= 1;
        if in_deg[v] == 0 {
          queue.push_back(v);
        }
      }
    }
    // Propagate ancestors in topological order
    let mut ancestors: Vec<BTreeSet<i32>> = vec![BTreeSet::new(); n];
    for v in topo {
      let parents: Vec<usize> = radj[v].clone();
      for u in parents {
        ancestors[v].insert(u as i32);
        let anc_u: Vec<i32> = ancestors[u].iter().cloned().collect();
        for a in anc_u {
          ancestors[v].insert(a);
        }
      }
    }
    ancestors.into_iter().map(|s| s.into_iter().collect()).collect()
  }
}