Validate a DFS Traversal Order
Problem statement
Given a connected, simple, undirected graph on vertices 0 through n-1, determine whether order can be the complete DFS preorder starting at vertex 0.
A recursive DFS records a vertex when first visiting it, then explores each unvisited neighbor fully before returning. Each vertex may choose any order for its neighbors. Return true if some choices produce exactly the supplied order. Return false for a wrong length, repeated or out-of-range vertex, or a different starting vertex.
Function
isValidDfsOrder(n: int, edges: int[][], order: int[]) → booleanExamples
Example 1
n = 10edges = [[0,5],[5,1],[5,4],[1,8],[4,9],[4,7],[4,2],[2,3],[2,6]]order = [0,5,1,8,4,7,9,2,3,6]return = trueFinish vertex 1 and its child 8 before returning to 5, then explore the entire subtree of 4.
Example 2
n = 10edges = [[0,5],[5,1],[5,4],[1,8],[4,9],[4,7],[4,2],[2,3],[2,6]]order = [0,8,1,5,4,7,9,2,3,6]return = falseVertex 0 has only neighbor 5, so vertex 8 cannot be visited second.
Example 3
n = 4edges = [[0,1],[0,2],[1,3],[2,3]]order = [0,1,2,3]return = falseFrom vertex 1, unvisited neighbor 3 must be explored before returning toward vertex 2.
Constraints
1 <= n <= 2000;n-1 <= edges.length <= min(10000,n*(n-1)/2).- Every edge has two different valid vertices; no duplicate undirected edge exists, and the graph is connected.
0 <= order.length <= 2001; each order entry is a signed 32-bit integer.