Simple chain
Input
n = 4, edges = [(0,1), (1,2), (2,3)]
Output
[0, 1, 2, 3]
Each node depends on the previous, so the only valid ordering is [0,1,2,3].
Full lesson preview
Perform topological sort using Kahn’s algorithm
Implement Kahn's algorithm to produce a valid topological ordering of a directed acyclic graph (DAG). If the graph has a cycle, return an empty list.
Python practice25 minStacks & QueuesAdvancedLast updated March 27, 2026
Problem statement
Given n nodes labeled from 0 to n-1 and a list of directed edges (u, v) indicating an edge from u to v, return a list representing a topological ordering of the nodes if one exists. If the directed graph contains a cycle (no valid topological ordering), return an empty list. Implement Kahn's algorithm (BFS-based) for topological sorting and make the output deterministic by always selecting the smallest-numbered node among nodes with zero in-degree.
Task
Write a function that returns one valid topological ordering for a graph represented by number of nodes and a list of directed edges. Use Kahn's algorithm and ensure deterministic output by always choosing the smallest available node next.
Examples
Input format
Two arguments: an integer n (number of nodes) and a list of pairs edges where each pair (u, v) is a directed edge from u to v.
Output format
A list of integers representing a valid topological ordering, or an empty list if no ordering exists (cycle).
Constraints
0 <= n <= 10^4, 0 <= number of edges <= 10^5. Nodes are labeled 0..n-1. Edges may form cycles.
Samples
Sample 1
Input
n = 6, edges = [(5,2), (5,0), (4,0), (4,1), (2,3), (3,1)]
Output
[4, 5, 0, 2, 3, 1]
Kahn's algorithm picking smallest available node first yields the deterministic order [4,5,0,2,3,1].