Practice/Amazon/Leetcode 2192. All Ancestors of a Node in a Directed Acyclic Graph

Leetcode 2192. All Ancestors of a Node in a Directed Acyclic Graph

CodingOptional

Problem

You are given a directed acyclic graph (DAG) with n nodes labeled from 0 to n - 1, and an array of edges where each edges[i] = [from, to] represents a directed edge from node from to node to.

Your task is to determine, for each node in the graph, which nodes can reach it by following directed edges. In other words, find all ancestors of each node. An ancestor of node x is any node y such that there exists a directed path from y to x.

Return a list where the element at index i contains a sorted list of all ancestors of node i.

Requirements

1. Build the ancestry information for every node in the graph
2. For each node, include all nodes that can reach it (not just direct parents)
3. Return the ancestors in sorted ascending order for each node
4. Handle graphs with no edges and graphs with complex connectivity patterns

Constraints

• 1 <= n <= 1000
• 0 <= edges.length <= min(2000, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= from, to < n
• from != to
• There are no duplicate edges
• The graph is a valid DAG (no cycles)

Examples

Example 1:

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

Explanation:

• Node 0: No ancestors
• Node 1: Can be reached from node 0
• Node 2: Can be reached from node 0
• Node 3: Can be reached from nodes 0 (via 1 or 2), 1, and 2
• Node 4: Can be reached from nodes 0 (via 2) and 2 `

Example 2:

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

Explanation: This is a simple chain where each node inherits all ancestors from its predecessor. `

Example 3:

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

Explanation: Node 2 has two direct parents (0 and 1), and they become its ancestors. `