975. DFS Traversal of Undirected Graph

Given an undirected graph with n nodes and a list of edges, perform a depth-first search from a given start node, always visiting 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 from node 0.

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

Input: {"n":3,"edges":[[0,1],[1,2]],"start":1}
Output: [1,0,2]
Explanation: Explore 0 before 2.

Constraints

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

Asked by