Return the Lexicographically Smallest Topological Order

Problem Statement

You are given an integer n, representing n tasks labeled from 0 to n - 1, and a list of directed dependencies edges, where edges[i] = [u, v] indicates that task u must be performed before task v (u -> v).

A valid topological ordering is a sequence of all n tasks such that for every directed edge u -> v, task u appears before task v in the sequence.

Among all valid topological orderings, return the lexicographically smallest one. If the graph contains a directed cycle (making a valid topological ordering impossible), return an empty list [].

Note:

• edges may contain duplicate pairs or self-loops.
• If multiple tasks are simultaneously eligible to be processed (i.e., they have zero remaining incoming dependencies), always select the one with the smallest integer label.

Function Signature

def get_lexicographically_smallest_order(n: int, edges: list[list[int]]) -> list[int]:
    pass

Constraints

• 1 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• 0 <= u, v < n for all [u, v] in edges

Examples

Example 1

Input: n = 4, edges = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [3, 1, 2, 0]
Explanation:
- Valid topological orderings include [3, 1, 2, 0] and [3, 2, 1, 0].
- At the start, only node 3 has an in-degree of 0.
- After node 3 is processed, nodes 1 and 2 both have an in-degree of 0.
- Node 1 is smaller than node 2, so node 1 is chosen next.
- Node 2 is chosen next, followed finally by node 0.
- [3, 1, 2, 0] is the lexicographically smallest ordering.

Example 2

Input: n = 3, edges = [[0, 1], [1, 2], [2, 0]]
Output: []
Explanation: The graph contains a cycle (0 -> 1 -> 2 -> 0), so no valid ordering exists.

Example 3

Input: n = 5, edges = [[0, 2], [0, 2], [1, 3]]
Output: [0, 1, 2, 3, 4]
Explanation:
Duplicate edge [0, 2] is ignored for in-degree calculations. Node 4 is isolated and has in-degree 0 initially.