← Back to DSA Animator
Course Schedule II LC #210 Medium Graph · Kahn's Topological Sort
Problem

Return a topological order of courses. prerequisites[i]=[a,b] means take b before a. Return [] if impossible (cycle).

Example
Input: n=2, prereqs=[[1,0]]
Output: [0,1]
Try Examples
Custom: n / prereqs (a-b)
Approach
Kahn's Algorithm (BFS Topological Sort)
In-degree 0 = no prerequisites. Process node → decrement neighbors' inDeg → enqueue new 0-degree nodes. idx==n iff no cycle.
Graph & inDeg / Order
Load an example.
Variables
u (process)
—
Queue
—
Order
—
idx
—
Step Logic
Press ▶ Play or Next Step.
✓
Ready
0/0
Select example and Play.
Algorithm
1
Enqueue all inDeg=0
2
Poll u, add to order, decrement neighbors
3
Return order if idx==n else []
Time
O(V+E)
Space
O(V)
Why Kahn's

In-degree 0 = can take now. After taking a course, decrement inDeg of dependents. New 0s get enqueued. Cycle → some nodes never reach 0 → idx<n.