Topological sort (Kahn)

Course scheduling via in-degree.

graph BFS topological-sort

Implement `topo_sort(n: int, edges: list[tuple[int,int]]) -> list[int]`.

Nodes are 0..n-1. edge (a,b) means a must come before b. Return any valid ordering or [] for cycles.

Constraints

1 ≤ n ≤ 10^4; 0 ≤ len(edges) ≤ 10^5

Example

>>> topo_sort(4, [(0,1),(0,2),(1,3),(2,3)])
[0, 1, 2, 3]  # or [0, 2, 1, 3]

45 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build in-degree array; start with zero-in-degree nodes; BFS reduce in-degrees.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.