Smallest Valid Task Order from Dependency Pairs (Topological Sort)

A project consists of n tasks labeled 0 to n - 1, done one at a time. Some tasks depend on others: a dependency pair [a, b] means task a must be finished before task b can start.

Return an order in which all n tasks can be done without violating any dependency. Several orders may be valid; return the lexicographically smallest one. If the dependencies make it impossible to finish every task, return an empty list.

Function Signature

def task_order(n: int, dependencies: list[list[int]]) -> list[int]:

dependencies[i] = [a, b] means task a must come before task b.

Rules

• A valid order contains every task from 0 to n - 1 exactly once, and for every pair [a, b], task a appears before task b.
• Order x is lexicographically smaller than order y if, at the first index where they differ, x has the smaller task label.
• If no valid order exists because the dependencies contain a cycle, return [].
• The same pair may appear more than once; duplicates express the same constraint.

Constraints

• 1 <= n <= 10^5
• 0 <= len(dependencies) <= 2 * 10^5
• Each dependencies[i] has exactly two elements [a, b]
• 0 <= a <= n - 1, 0 <= b <= n - 1, and a != b

Examples

Example 1

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

Task 3 must precede tasks 1 and 2, and both of those must precede task 0. The valid orders are [3, 1, 2, 0] and [3, 2, 1, 0]; the first is lexicographically smaller.

Example 2

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

Task 2 must precede task 0, and task 1 is unconstrained. The valid orders are [1, 2, 0], [2, 0, 1] and [2, 1, 0], and the smallest is [1, 2, 0]. Task 0 cannot come first even though it has the smallest label.

Example 3

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

Each of the three tasks must come before the next one around a cycle, so no order satisfies all three pairs.