 All Problems
All Ancestors of a Node in a Directed Acyclic Graph
medium
topological sort
graph
bfs
dfs
google
amazon
microsoft

You are given a DAG with n nodes (0 to n-1) and a list of directed edges. For each node i, return a sorted list of all its ancestors (nodes that have a path to i).

Example:

Input: n=8, edgeList=[[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]

Constraints:

  • 1 <= n <= 1000
  • 0 <= edgeList.length <= min(2000, n*(n-1)/2)
Run to check your code against the sample cases, or submit to run every case