Smallest Topological Order
You are given a directed graph with no cycles with n vertices numbered 0 to n - 1, and a list edges. Each edge [u, v] means that u must come before v.
A topological order is a list of all n vertices, each one exactly once, where for every edge [u, v] the vertex u comes before v.
A graph can have many topological orders. Return the one that is smallest in dictionary order: compare two orders number by number from the start, and the first position where they differ decides. The order with the smaller number there is smaller.
Note
- This rule makes the answer unique: there is exactly one smallest order.
- The graph is guaranteed to have no cycle, so at least one topological order exists.
- No edge appears twice, and no edge goes from a vertex to itself.
Hint: at each step, the vertices you can place next are the ones whose earlier vertices are all already placed. Always place the smallest of them. A min-heap keeps that cheap.
Examples
Example 1
- Input:
- 5, [[3,0],[0,2],[4,2]]
- Output:
- [1,3,0,4,2]
At the start, vertices 1, 3 and 4 have nothing that must come before them. Vertex 1 is the smallest, so it goes first. Then 3 and 4 are ready, so 3 goes next. That makes 0 ready, and 0 is smaller than 4. Then 4, and last 2, which needed both 0 and 4.
Example 2
- Input:
- 4, []
- Output:
- [0,1,2,3]
With no edges every order is valid, and the smallest one is simply 0, 1, 2, 3.
Example 3
- Input:
- 3, [[2,1],[1,0]]
- Output:
- [2,1,0]
The edges force one chain: 2 before 1 and 1 before 0. Only one order is valid.
Constraints
1 <= n <= 100 <= edges.length <= 45edges[i] = [u, v]with0 <= u, v < nandu != v- The graph has no cycle, and no edge appears twice.
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.