You are given a DAG with n nodes 0 .. n-1 and directed edges edges ([u, v] is an edge from u to v). Node u is an ancestor of v if v is reachable from u by following one or more edges.
Return a list res of length n where res[v] is the sorted list of all ancestors of v (an empty list if it has none).
Examples
Input: n = 5, edges = [[0, 3], [1, 3], [3, 4], [2, 4]]
Output: [[], [], [], [0, 1], [0, 1, 2, 3]]
Constraints
1 <= n <= 1000,0 <= len(edges) <= 2000, no cycles, no duplicate edges- Target: O(n * (n + E)) time or better.
Goals
- Propagate ancestor sets forward along a topological order
- Produce sorted output for every node, including nodes with no ancestors