Alphabetical Build Order (Kahn)
Implement smallestOrder
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. Many orders can satisfy the dependencies; return the lexicographically smallest one.
Kahn's algorithm builds the order from the front: tasks that nothing is waiting on are ready, and finishing a task may make further tasks ready. Choosing the smallest ready task each time yields the smallest order.
Example 1:
Input: graph = [[],[],[3],[1],[0,1],[0,2]]
Output: [4,5,0,2,3,1]
Example 2:
Input: graph = [[],[],[]]
Output: [0,1,2]
Example 3:
Input: graph = [[],[0]]
Output: [1,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 - ●
A valid order lists all tasks so that for every road u → v, task u appears before task v - ●
Many valid orders may exist: return the lexicographically smallest one (the first position holds the smallest possible task number, then the second, and so on)
graph =
[[], [], [3], [1], [0,1], [0,2]]