977. DFS Traversal of Directed Graph

Given a directed graph with n nodes and a list of directed edges [u, v], perform a depth-first search from a given start node, always following out-neighbors in ascending order. Return the order in which nodes are first visited as an array. The input is JSON {n, edges, start}.

Input: JSON {n, edges, start}.

Output: Array — the DFS visitation order.

Examples

Input: {"n":5,"edges":[[0,1],[0,2],[1,3],[2,4]],"start":0}
Output: [0,1,3,2,4]
Explanation: Depth-first over directed edges.

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

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

Constraints

• 1<=n<=10^5
• directed
• 0<=start<n

Asked by