Lexicographically Smallest Topological Order of a Dependency Graph

You are given a dependency graph with `n` nodes labeled `0` to `n - 1` and a list of directed edges, where an edge `[u, v]` means node `u` must come before node `v`. Return an ordering of all `n` nodes in which, for every edge, `u` appears before `v`. If no such ordering exists because the edges contain a cycle, return an empty list. Many graphs have more than one valid ordering. Return the lexicographically smallest one: compare two valid orderings at the first position where they differ; the ordering with the smaller label at that position is the smaller one. ### Function Signature ```python def topological_order(n: int, edges: list[list[int]]) -> list[int]: ``` ### Rules - Every node appears exactly once in the result, including nodes that have no edges. - An edge may be listed more than once; repeats mean the same as a single copy. - A self-loop `[u, u]` is a cycle. - If any cycle exists anywhere in the graph, return `[]`, even if some nodes could still be ordered. ### Constraints - `1 <= n <= 10^5` - `0 <= len(edges) <= 2 * 10^5` - each edge is a pair `[u, v]` with `0 <= u < n` and `0 <= v < n` ### Examples **Example 1** ```text Input: n = 5, edges = [[3, 1], [1, 0], [3, 2], [4, 2]] Output: [3, 1, 0, 4, 2] ``` Only 3 and 4 have no prerequisites, so the ordering starts with 3. After 3, both 1 and 4 are allowed and 1 is smaller; after 1, node 0 is allowed and is smaller than 4. Node 2 must wait for both 3 and 4. **Example 2** ```text Input: n = 3, edges = [[0, 1], [1, 2], [2, 0]] Output: [] ``` The three edges form a cycle, so no valid ordering exists. **Example 3** ```text Input: n = 4, edges = [[2, 0], [2, 0], [1, 3]] Output: [1, 2, 0, 3] ``` The repeated edge `[2, 0]` counts once. Node 0 has the smallest label but must follow 2, and node 3 must follow 1.