The One Valid Build Order (DFS)
Implement buildOrder
You are given a set of tasks with dependencies, described as an adjacency list of a directed graph with no cycles: a road u → v means task v can only start after task u finishes. Return an order in which all tasks can be done. In this version the dependencies are so tight that only one order is possible, so every correct method returns the same list.
The depth-first approach records each task when the search is completely done with it; the reverse of that list is a valid order (a topological order).
Example 1:
Input: graph = [[3,5],[4],[0,3],[1,5],[],[1]]
Output: [2,0,3,5,1,4]
Example 2:
Input: graph = [[1],[]]
Output: [0,1]
Example 3:
Input: graph = [[]]
Output: [0]
+ 14 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 8 tasks numbered 0 … n-1; graph[u] lists, in increasing order, every task v that can only start after task u has finished (adjacency-list form of a directed graph) - ●
The graph has no cycles, and the tasks can be arranged in exactly ONE valid order (every task is forced by the roads) - ●
A valid order lists all tasks so that for every road u → v, task u appears before task v - ●
Return that order
graph =
[[3,5], [4], [0,3], [1,5], [], [1]]