All Ancestors of a Node in a DAG

Given a DAG, return for every node the sorted list of all its ancestors. Pattern focus: DFS Topological Order. Propagating ancestor sets along a topological order is a standard DAG technique.

Input Format

n = number of vertices, edges = directed edge list

Output Format

for each node, the sorted list of its ancestors

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9

Examples

Example 1:

Input:

n = 8
edges = [[0,3],[0,4],[1,3],[2,4],[3,5],[3,6],[4,6],[5,7],[6,7]]

Output:

[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3,4,5,6]]

Explanation:

Each node's ancestors are all vertices that can reach it.

Example 2:

Input:

n = 3
edges = [[0,1],[1,2]]

Output:

[[],[0],[0,1]]

Explanation:

The chain 0 -> 1 -> 2 gives increasing ancestor sets.

Example 3:

Input:

n = 1
edges = []

Output:

[[]]

Explanation:

A single node has no ancestors.

Loading...
All Ancestors of a Node in a DAG