All Ancestors of a Node in a Directed Acyclic Graph

Challenge Points: 20

Level: Medium

You are given a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n - 1.
The connections in the graph are given through the list edges, where each entry [u, v] represents a directed edge from node u to node v.

Your task is to determine, for each node i, all nodes that can reach i by following directed edges.
These nodes are called ancestors of i.

Return the result as a list answer of size n, where answer[i] contains all ancestors of node i sorted in ascending order.

Example 1:

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

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

Explanation:

Chain: 0 → 1 → 2 → 3

Example 2:

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

Output: [ [], # Node 0 has no ancestors [], # Node 1 has no ancestors [0,1], # Both 0 and 1 can reach 2 [], # Node 3 has no ancestors [0,1,2,3],# Paths: 0→2→4, 1→2→4, 3→4 [0,1,2,3,4] # All ancestors of node 4 plus 4 itself leads to 5 ]

Explanation:

Graph: 0 → 2 → 4 → 5 1 → 2 3 → 4

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result