All Ancestors of a Node in a Directed Acyclic Graph

For every node, list everyone who can reach it. That list is its ancestors. This is a reachability question dressed up as a family tree. The clean trick is to ask it backwards: start from each node and mark everyone it can reach.

🎯 The Problem

You get a directed acyclic graph, a graph where edges have a direction and no path ever loops back to its start. Here are the rules.

• You get the number of nodes and a list of directed edges.
• An edge [from, to] means you can move from from to to.
• For each node, return the sorted list of its ancestors.
• An ancestor of node x is any node from which you can reach x by following one or more edges.
• Each list must be sorted and hold no duplicates.

Input:
  n = 5
  edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]

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

Explanation:
  Node 3 can be reached from 0, 1, and 2.
  Node 4 can be reached from everyone before it.

Here is the graph. Arrows point from a parent toward a child.

🐢 Approach 1: Search Down From Every Source (Brute Force)

The idea in one line: flip the question and search down from each node to mark everyone it reaches.

The idea:

• Instead of finding who reaches node x, find who x can reach.
• Those two views are the same fact seen from opposite ends.
• If 0 can reach 3, then 0 is an ancestor of 3.

How it works:

• Pick each node as a source, the starting node of a search.
• Run a search down its edges.
• Every node you land on can be reached from the source, so add the source to that node’s ancestor list.
• Mark nodes visited within one source’s search so you do not revisit them.
• After all searches, each node holds the set of sources that reached it. Sort each set.

Why it is weak:

• You run a full search once per node.
• That repeats work across sources.
• The worst case is O(V × (V + E)). Fine for interview-sized graphs, but not the tightest.

Here is the search-from-every-source code:

def get_ancestors(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
    ans = [set() for _ in range(n)]
    def dfs(src, node):
        for nei in graph[node]:
            if src not in ans[nei]:
                ans[nei].add(src)
                dfs(src, nei)
    for src in range(n):
        dfs(src, src)
    return [sorted(group) for group in ans]

🚀 Approach 2: Reverse Topological Build (Better)

The idea in one line: process nodes in topological order so each child inherits its parents’ ancestor sets.

The idea:

• Topological order lists a DAG so every node comes before the nodes it points to.
• Process nodes in that order.
• A child inherits all of its parents’ ancestors plus the parents themselves.

How it works:

• Build each ancestor set from the sets already computed before it.
• No need to start a fresh search for every node.

Why it is mixed:

• It avoids the redundant searches.
• But you must merge sets carefully and keep them sorted or deduped.
• The search-from-each-source version is simpler to write across five languages, so we code that one.
• Both reach the same answer.

Here is one source search. Starting from node 0, every node it touches gains 0 as an ancestor.

Steps to Solve

1. Build a graph as adjacency lists from the edges.
2. For each node, treat it as the source and run a depth-first search down its edges.
3. Mark nodes visited within this one search so you do not loop or repeat.
4. For every node you reach, record the source as one of its ancestors.
5. After all searches, sort each node’s ancestor list.
6. Return the lists.

#include <stdio.h>

#define N 5
int adj[N][N];
int isAnc[N][N];   // isAnc[node][src] = 1 if src is an ancestor of node
int visited[N];

void dfs(int node, int src) {
    for (int v = 0; v < N; v++)
        if (adj[node][v] && !visited[v]) {
            visited[v] = 1;
            isAnc[v][src] = 1;   // src can reach v
            dfs(v, src);
        }
}

int main(void) {
    int edges[5][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
    for (int i = 0; i < 5; i++) adj[edges[i][0]][edges[i][1]] = 1;

    for (int src = 0; src < N; src++) {
        for (int i = 0; i < N; i++) visited[i] = 0;
        dfs(src, src);           // search down from src
    }

    for (int node = 0; node < N; node++) {
        printf("%d: [", node);
        int first = 1;
        for (int a = 0; a < N; a++)   // a < N keeps the list sorted
            if (isAnc[node][a]) {
                if (!first) printf(", ");
                printf("%d", a);
                first = 0;
            }
        printf("]\n");
    }
    return 0;
}

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

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<vector<int>> adj;
vector<set<int>> ancestors;
vector<bool> visited;

void dfs(int node, int src) {
    for (int v : adj[node])
        if (!visited[v]) {
            visited[v] = true;
            ancestors[v].insert(src);   // src reaches v
            dfs(v, src);
        }
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
    adj.assign(n, {});
    ancestors.assign(n, {});
    for (auto& e : edges) adj[e[0]].push_back(e[1]);

    for (int src = 0; src < n; src++) {
        visited.assign(n, false);
        dfs(src, src);
    }

    for (int node = 0; node < n; node++) {
        cout << node << ": [";
        bool first = true;
        for (int a : ancestors[node]) {   // a set iterates in sorted order
            if (!first) cout << ", ";
            cout << a;
            first = false;
        }
        cout << "]\n";
    }
    return 0;
}

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

import java.util.*;

public class AllAncestors {
    static List<List<Integer>> adj;
    static List<TreeSet<Integer>> ancestors;
    static boolean[] visited;

    static void dfs(int node, int src) {
        for (int v : adj.get(node))
            if (!visited[v]) {
                visited[v] = true;
                ancestors.get(v).add(src);   // src reaches v
                dfs(v, src);
            }
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
        adj = new ArrayList<>();
        ancestors = new ArrayList<>();
        for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); ancestors.add(new TreeSet<>()); }
        for (int[] e : edges) adj.get(e[0]).add(e[1]);

        for (int src = 0; src < n; src++) {
            visited = new boolean[n];
            dfs(src, src);
        }

        for (int node = 0; node < n; node++)
            System.out.println(node + ": " + new ArrayList<>(ancestors.get(node)));
    }
}

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

def all_ancestors(n, edges):
    adj = [[] for _ in range(n)]            # adj[u] = nodes u points to
    for u, v in edges:
        adj[u].append(v)

    ancestors = [set() for _ in range(n)]   # ancestors[node] = sources that reach it

    def dfs(node, src, visited):
        for nxt in adj[node]:
            if nxt not in visited:
                visited.add(nxt)
                ancestors[nxt].add(src)     # src can reach nxt
                dfs(nxt, src, visited)

    for src in range(n):
        dfs(src, src, set())                # search down from each source

    return [sorted(ancestors[node]) for node in range(n)]


n = 5
edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
result = all_ancestors(n, edges)
for node in range(n):
    print(f"{node}: {result[node]}")

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

function allAncestors(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) adj[u].push(v);

  const ancestors = Array.from({ length: n }, () => new Set());

  function dfs(node, src, visited) {
    for (const nxt of adj[node]) {
      if (!visited.has(nxt)) {
        visited.add(nxt);
        ancestors[nxt].add(src); // src can reach nxt
        dfs(nxt, src, visited);
      }
    }
  }

  for (let src = 0; src < n; src++) dfs(src, src, new Set());

  return ancestors.map((set) => [...set].sort((a, b) => a - b));
}

const n = 5;
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]];
const result = allAncestors(n, edges);
for (let node = 0; node < n; node++) {
  console.log(`${node}: [${result[node].join(", ")}]`);
}

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

Let us read the Python version line by line, because the flipped view is the whole insight.

adj = [[] for _ in range(n)] makes one empty neighbor list per node. The loop fills it. adj[u].append(v) records that u points to v.

ancestors = [set() for _ in range(n)] gives each node an empty set. A set keeps each ancestor once, so we never store a duplicate.

dfs(node, src, visited) walks down from the current node. For each neighbor nxt we have not seen in this search, we mark it visited, record that src reached it, and recurse. The line ancestors[nxt].add(src) is the core. We are not recording who node reaches. We record that the original src reaches nxt. That is why we carry src through the whole recursion unchanged.

The visited set belongs to one source’s search. We pass a fresh set() each time we start a new source. So node 4 can be reached and recorded once per source, but never twice within the same source’s walk.

The main loop runs dfs(src, src, set()) for every node. After all of them, each node’s set holds every source that could reach it. That set is exactly its ancestors.

The final line sorts each set. The problem wants each ancestor list in increasing order, and sorted gives that.

⏱️ Time and Space Complexity

We run one DFS per node. Each DFS can touch every node and edge, so it is O(V + E). With V sources that is O(V × (V + E)). The reverse topological build avoids repeated work but spends time merging sets. We store an adjacency list plus an ancestor set per node, so space is O(V + E) plus the size of the answer.

🧩 Key Takeaways

• ✅ An ancestor of x is any node that can reach x along the edges.
• ✅ Flip the question. Search down from each source and mark every node it reaches.
• ✅ The source is an ancestor of every node its search lands on.
• ✅ Use a set per node so ancestors stay unique, then sort each set.
• ✅ Carry the original source through the recursion, not the current node.

🚀 What’s Next?

• Bus Routes
• Evaluate Division