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

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

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

Input: n = 3, edges = [[0, 1], [1, 2], [2, 0]]
Output: []

The three edges form a cycle, so no valid ordering exists.

Example 3

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.