1043. Find All Ancestors of a Node in DAG

Given a directed acyclic graph with n nodes and edges [u, v] (an edge from u to v), return for each node the sorted list of its ancestors — all nodes that can reach it via a directed path. Return the answer as a nested array indexed by node. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Nested array — sorted ancestors per node.

Examples

Input: {"n":5,"edges":[[0,3],[0,4],[1,3],[2,4],[2,3]]}
Output: [[],[],[],[0,1,2],[0,2]]
Explanation: Ancestors of each node.

Input: {"n":1,"edges":[]}
Output: [[]]
Explanation: No ancestors.

Input: {"n":3,"edges":[[0,1],[1,2]]}
Output: [[],[0],[0,1]]
Explanation: Chain ancestors.

Constraints

• 1<=n<=1000
• directed acyclic

Asked by