1012. Topological Sort Using DFS

Given a directed acyclic graph (DAG) with n nodes and a list of directed edges, return a topological ordering produced by DFS: run DFS from nodes 0..n-1 in ascending order (visiting each node's out-neighbors in ascending order), append each node when its DFS finishes, then reverse that finish order. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Array — a DFS-based topological order.

Examples

Input: {"n":6,"edges":[[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]]}
Output: [5,4,2,3,1,0]
Explanation: Reverse DFS finish order.

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

Input: {"n":1,"edges":[]}
Output: [0]
Explanation: Single node.

Constraints

• 1<=n<=10^5
• graph is a DAG

Asked by