Return a topological ordering of a graph

Task

Given a directed graph represented as a list of n tasks (labeled 0 to n-1) and a list of prerequisites where prerequisites[i] = [a, b] indicates that task b must be completed before task a, return a valid ordering of tasks. If no such ordering exists (i.e., there is a cycle), return an empty list.

Function Signature

def find_order(n: int, prerequisites: list[list[int]]) -> list[int]:

Constraints

• 1 <= n <= 2000
• 0 <= len(prerequisites) <= n * (n - 1) / 2
• All prerequisite pairs are unique.

Examples

Example 1:

• Input: n = 2, prerequisites = [[1, 0]]
• Output: [0, 1]
• Explanation: Task 0 must be done before 1.

Example 2:

• Input: n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
• Output: [0, 1, 2, 3] (or [0, 2, 1, 3])
• Explanation: 0 is the root, followed by 1 and 2, and finally 3.

Example 3:

• Input: n = 2, prerequisites = [[1, 0], [0, 1]]
• Output: []
• Explanation: A cycle exists, so no valid order is possible.

Edge Cases

• Disconnected graphs (multiple components).
• Graphs with no prerequisites (any order is valid).
• Graphs containing self-loops or complex cycles.