Get started

All Ancestors of a Node in a Directed Acyclic Graph — Medium Problem & Solution

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.

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 85 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Graph Data Structure