All Ancestors of a Node in a Directed Acyclic Graph

medium topological sort dag

Problem

You are given a directed acyclic graph with n nodes labeled 0 to n − 1 (1 ≤ n ≤ 1000) and a list of edges where [u, v] denotes a directed edge from u to v. A node u is an ancestor of v if u can reach v by following one or more directed edges.

Return a list answer where answer[i] holds all distinct ancestors of node i sorted in ascending order. The graph has no cycles and no duplicate edges.

Inputn = 8, edges = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]

Output[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]

Nodes 0, 1 and 2 have no incoming edges, so no ancestors; node 6 can be reached from 0, 1, 2, 3 and 4.

n (nodes, 2..8)

edges (JSON list of [from, to] pairs)

from collections import deque

def get_ancestors(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    anc = [set() for _ in range(n)]
    q = deque(i for i in range(n) if indeg[i] == 0)
    while q:
        u = q.popleft()
        for v in adj[u]:
            anc[v].add(u)
            anc[v] |= anc[u]
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return [sorted(a) for a in anc]

function getAncestors(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) {
    adj[u].push(v);
    indeg[v]++;
  }
  const anc = Array.from({ length: n }, () => new Set());
  const q = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  for (let head = 0; head < q.length; head++) {
    const u = q[head];
    for (const v of adj[u]) {
      anc[v].add(u);
      for (const a of anc[u]) anc[v].add(a);
      if (--indeg[v] === 0) q.push(v);
    }
  }
  return anc.map(s => [...s].sort((a, b) => a - b));
}

List<List<Integer>> getAncestors(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    List<TreeSet<Integer>> anc = new ArrayList<>();
    int[] indeg = new int[n];
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
        anc.add(new TreeSet<>());
    }
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        indeg[e[1]]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            anc.get(v).add(u);
            anc.get(v).addAll(anc.get(u));
            if (--indeg[v] == 0) q.add(v);
        }
    }
    List<List<Integer>> res = new ArrayList<>();
    for (TreeSet<Integer> s : anc) res.add(new ArrayList<>(s));
    return res;
}

vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    vector<set<int>> anc(n);
    vector<int> indeg(n, 0);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        indeg[e[1]]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            anc[v].insert(u);
            anc[v].insert(anc[u].begin(), anc[u].end());
            if (--indeg[v] == 0) q.push(v);
        }
    }
    vector<vector<int>> res(n);
    for (int i = 0; i < n; i++) res[i] = vector<int>(anc[i].begin(), anc[i].end());
    return res;
}

Explanation

The key insight is that ancestor information flows along the edges: every ancestor of node v is either a direct parent p, or an ancestor of that parent. So anc[v] is the union of {p} ∪ anc[p] over all parents p. To use that formula safely we must only hand a node's set to its children once the set is complete — which is exactly what processing nodes in topological order guarantees, because every path into v is fully accounted for before v is popped.

We run Kahn's algorithm: build the adjacency list and an indegree counter, seed a queue with all indegree-0 sources (they have no ancestors by definition), then repeatedly pop a node u. For each child v we insert u itself plus everything in anc[u] into anc[v], and decrement indeg[v]; when it hits zero, all of v's parents are done, so v joins the queue with its ancestor set final.

On the default example the sources are 0, 1, 2. Popping 0 stamps {0} onto nodes 3 and 4; popping 1 grows anc[3] to {0,1} and releases node 3; popping 2 completes anc[4] = {0,2} and starts anc[7] = {2}. Node 3 then forwards {3} ∪ {0,1} to 5, 6 and 7, and node 4 forwards {4} ∪ {0,2} to 6, giving anc[6] = {0,1,2,3,4} — every set is finished exactly when its node leaves the queue.

Sets (hash sets, or TreeSet/std::set which keep order for free) are essential because several paths can reach the same node — node 6 receives 0 from both the path through 3 and the path through 4, but must report it once. A final sort per node produces the required ascending output.

An equally valid alternative runs a DFS or BFS from each node u and appends u to the answer list of every node it reaches; iterating u in increasing order even yields the lists pre-sorted. Both approaches are O(n·(n + m)).

Complexity: each of the m edges can carry a set of up to n ancestors across it, so the propagation costs O(n·(n + m)) time, and storing one ancestor set per node takes O(n²) space in the worst case.

Time: O(n·(n + m)) Space: O(n²)