All Ancestors of a Node in a Directed Acyclic Graph

All Ancestors of a Node in a Directed Acyclic Graph - Problem

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [from_i, to_i] denotes that there is a unidirectional edge from from_i to to_i in the graph.

Return a list answer, where answer[i] is the list of ancestors of the i^th node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

Input & Output

Example 1 — Basic DAG

$ Input: n = 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,3,4],[0,1,2,3]]

💡 Note: Node 3 has ancestors [0,1] because both 0→3 and 1→3. Node 7 has ancestors [0,1,2,3] because all can reach it through various paths.

Example 2 — Simple Chain

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

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

💡 Note: Linear chain: each node has all previous nodes as ancestors.

Example 3 — No Edges

$ Input: n = 3, edges = []

› Output: [[],[],[]]

💡 Note: No edges means no node can reach any other, so no ancestors exist.

Constraints

1 ≤ n ≤ 1000
0 ≤ edges.length ≤ min(2000, n × (n - 1) / 2)
edges[i].length == 2
0 ≤ from_i, to_i ≤ n - 1
from_i ≠ to_i
There are no duplicate edges.
The graph is acyclic.

Visualization

Tap to expand

Understanding the Visualization

Input DAG

Directed acyclic graph with nodes and edges

Find Paths

For each node, find all nodes that can reach it

Output Lists

Return sorted ancestor lists for each node

Key Takeaway

🎯 Key Insight: Build reverse graph and use DFS to efficiently find all ancestor relationships

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to build a reverse graph where edges point from child to parent, then use DFS to find all reachable ancestors. The optimal approach uses reverse graph DFS with time complexity O(n(n+m)) and space O(n+m).

Common Approaches

Approach	Time	Space	Notes
✓ Reverse Graph DFS	O(n(n+m))	O(n+m)	Build reverse graph and run DFS from each node to find all reachable descendants
DFS from Each Node	O(n²(n+m))	O(n+m)	For each node, run DFS to find all nodes that can reach it

Reverse Graph DFS — Algorithm Steps

Build reverse adjacency list
For each node, run DFS to find all reachable nodes
The reachable nodes from node u are the descendants, so u is their ancestor

Visualization

Tap to expand

Step-by-Step Walkthrough

Reverse Edges

Build graph with reversed edge directions

DFS from Each Node

Find all nodes reachable in reverse graph

Ancestors Found

Reachable nodes are the ancestors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 1000

int reverseGraph[MAX_N][MAX_N];
int reverseGraphSize[MAX_N];
bool visited[MAX_N];
int ancestors[MAX_N];
int ancestorCount;

void dfs(int node) {
    for (int i = 0; i < reverseGraphSize[node]; i++) {
        int parent = reverseGraph[node][i];
        if (!visited[parent]) {
            visited[parent] = true;
            ancestors[ancestorCount++] = parent;
            dfs(parent);
        }
    }
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Initialize reverse graph
    for (int i = 0; i < n; i++) {
        reverseGraphSize[i] = 0;
    }
    
    // Read edges
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    // Parse edges
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            int u, v;
            sscanf(ptr+1, "%d,%d", &u, &v);
            reverseGraph[v][reverseGraphSize[v]++] = u;
        }
        ptr++;
    }
    
    printf("[");
    for (int node = 0; node < n; node++) {
        ancestorCount = 0;
        memset(visited, false, sizeof(visited));
        dfs(node);
        
        qsort(ancestors, ancestorCount, sizeof(int), compare);
        
        printf("[");
        for (int i = 0; i < ancestorCount; i++) {
            printf("%d", ancestors[i]);
            if (i < ancestorCount - 1) printf(",");
        }
        printf("]");
        if (node < n - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n(n+m))

For each of n nodes, we run DFS that visits at most n nodes and m edges

✓ Linear Growth

Space Complexity

O(n+m)

Reverse graph storage and DFS recursion stack

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Reverse Graph DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler