All Ancestors of a Node in a Directed Acyclic Graph

Medium
1535.

All Ancestors of a Node in a Directed Acyclic Graph

All Ancestors of a Node in a Directed Acyclic Graph is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon and Google interviews.

A directed acyclic graph has n nodes numbered 0 to n - 1; each edges[i] = [fromi, toi] is a one-way edge from fromi to toi.

Node u is an ancestor of node v if v can be reached from u by following one or more edges.

Return a list answer where answer[i] holds every ancestor of node i, sorted in ascending order.

Example 1

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

Example 2

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

Example 3

Input
n = 1, edges = []
Output
[[]]

Constraints

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • there are no duplicate edges
  • the graph is directed and acyclic
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var getAncestors = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

All Ancestors of a Node in a Directed Acyclic Graph Solution

All Ancestors of a Node in a Directed Acyclic Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

All Ancestors of a Node in a Directed Acyclic Graph is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon and Google interviews.

Problem statement

A directed acyclic graph has n nodes numbered 0 to n - 1; each edges[i] = [fromi, toi] is a one-way edge from fromi to toi.

Node u is an ancestor of node v if v can be reached from u by following one or more edges.

Return a list answer where answer[i] holds every ancestor of node i, sorted in ascending order.

Example 1

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

Example 2

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

Example 3

Input: n = 1, edges = []
Output: [[]]

Constraints

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • there are no duplicate edges
  • the graph is directed and acyclic

Hints for All Ancestors of a Node in a Directed Acyclic Graph

  1. Hint 1

    u is an ancestor of v exactly when a search starting at u reaches v.

  2. Hint 2

    Run a DFS or BFS from every node and record the source in the list of each node it reaches.

  3. Hint 3

    If you launch the searches from node 0, 1, 2, … in order, every list is filled in ascending order already — no sorting needed.

How to solve All Ancestors of a Node in a Directed Acyclic Graph

Instead of searching backwards from each node, search forwards from each potential ancestor: every node a search from s reaches gets s appended to its list.

Approach

  1. Build forward adjacency lists.
  2. For s = 0, 1, …, n − 1: run an iterative DFS from s with a fresh visited array.
  3. Every newly visited node v (other than s) gets s appended to answer[v].
  4. Return answer.

Why it works

s is appended to answer[v] exactly when v is reachable from s, which is the definition of an ancestor; the visited array ensures it is appended once. Because sources are processed in increasing order, each list receives its entries in increasing order.

Complexity

  • Time — O(n · (n + m))
  • Space — O(n + m) plus the output

Pitfalls

  • Reset the visited marks for each new source, or later sources miss nodes an earlier search already saw.
  • Nodes with no ancestors still need an (empty) entry in the answer.
  • Collecting ancestors by merging parents' sets also works but needs deduplication and sorting.

Reference solution

Python

from typing import List

def getAncestors(n: int, edges: List[List[int]]) -> List[List[int]]:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
    ans = [[] for _ in range(n)]
    for s in range(n):
        seen = [False] * n
        seen[s] = True
        stack = [s]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    ans[v].append(s)
                    stack.append(v)
    return ans

Java

public static int[][] getAncestors(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>(), anc = new ArrayList<>();
    for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); anc.add(new ArrayList<>()); }
    for (int[] e : edges) adj.get(e[0]).add(e[1]);
    int[] stack = new int[n + 1];
    for (int s = 0; s < n; s++) {
        boolean[] seen = new boolean[n];
        seen[s] = true;
        int top = 0;
        stack[top++] = s;
        while (top > 0) {
            int u = stack[--top];
            for (int v : adj.get(u)) {
                if (!seen[v]) { seen[v] = true; anc.get(v).add(s); stack[top++] = v; }
            }
        }
    }
    int[][] res = new int[n][];
    for (int v = 0; v < n; v++) {
        res[v] = new int[anc.get(v).size()];
        for (int k = 0; k < res[v].length; k++) res[v][k] = anc.get(v).get(k);
    }
    return res;
}

C++

vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n), ans(n);
    for (auto& e : edges) adj[e[0]].push_back(e[1]);
    vector<int> stack;
    for (int s = 0; s < n; s++) {
        vector<char> seen(n, 0);
        seen[s] = 1;
        stack.assign(1, s);
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            for (int v : adj[u]) {
                if (!seen[v]) { seen[v] = 1; ans[v].push_back(s); stack.push_back(v); }
            }
        }
    }
    return ans;
}

JavaScript

var getAncestors = function(n, edges) {
    var adj = [], ans = [];
    for (var i = 0; i < n; i++) { adj.push([]); ans.push([]); }
    for (var e = 0; e < edges.length; e++) adj[edges[e][0]].push(edges[e][1]);
    for (var s = 0; s < n; s++) {
        var seen = [];
        for (var k = 0; k < n; k++) seen.push(false);
        seen[s] = true;
        var stack = [s];
        while (stack.length > 0) {
            var u = stack.pop();
            for (var j = 0; j < adj[u].length; j++) {
                var v = adj[u][j];
                if (!seen[v]) { seen[v] = true; ans[v].push(s); stack.push(v); }
            }
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)