1013. Topological Sort Using Kahn's Algorithm (BFS)

Given a directed acyclic graph (DAG) with n nodes and a list of directed edges, return the lexicographically smallest topological ordering using Kahn's algorithm: repeatedly remove the smallest-labeled node with in-degree 0. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Array — the lexicographically smallest topological order.

Examples

Input: {"n":6,"edges":[[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]]}
Output: [4,5,0,2,3,1]
Explanation: Smallest available in-degree-0 node each step.

Input: {"n":3,"edges":[[0,1],[1,2]]}
Output: [0,1,2]
Explanation: Only one valid order.

Input: {"n":3,"edges":[]}
Output: [0,1,2]
Explanation: Sorted when no constraints.

Constraints

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

Asked by