0

Topological Sort (Kahn)

Medium

Repeatedly take any node with no remaining prerequisites. If you cannot empty the graph, there is a cycle.

indegreeDAGcycle detection
TimeO(V + E)
SpaceO(V)
Inputdirected edges u-v (u must come before v)
0011213241
queue
0

Indegrees counted. Nodes 0 have no prerequisites.

1 / 12
compute indegree for every node
queue = all nodes with indegree 0
while queue:
u = queue.pop(); order.push(u)
for v in adj[u]: if --indegree[v] == 0: queue.push(v)
if order.length < V: there is a cycle
Why it matters

The produced order being shorter than the node count is exactly the cycle test.

Practise this
Course ScheduleMCourse Schedule IIMAlien DictionaryH
Keyboard
space play← → stepr restartctrl K search

More in Graphs

Breadth First Search
O(V + E)
Depth First Search
O(V + E)
Dijkstra Shortest Path
O(E log V)
Union-Find (DSU)
Near O(1) amortised per operation
Kruskal Minimum Spanning Tree
O(E log E)
Flood Fill / Number of Islands
O(rows * cols)
Next visualiser
Union-Find (DSU)