Topological Sort
On this page
Some problems are about order under constraints: course B needs course A, package X needs package Y, letter t comes before f in an alien alphabet. Draw an arrow from "must happen first" to "happens after", and you have a directed graph. A topological order lists the nodes so that every arrow points forward. It exists exactly when the graph has no cycle, so the same algorithm answers "can all courses be finished?"
When to recognise it
- Prerequisites, dependencies, build order, "must come before".
- "Is it possible to finish / schedule all of them?": that means "is there a cycle?"
- "Return any valid order": the order itself.
- An ordering rule hidden in data: alien dictionary (compare neighbouring words), sequence reconstruction.
- "Minimum number of semesters / rounds": process Kahn's algorithm level by level and count the rounds.
How Kahn's algorithm works
Count, for every node, how many arrows point into it: its indegree, the number of things it still waits for. Start with every node whose indegree is 0. Each time you take one, remove its outgoing arrows; any node whose indegree drops to 0 is ready too.

Template
from collections import deque, defaultdict
def topo_order(n, edges):
"""Kahn's algorithm. edges are (before, after). Returns [] if there is a cycle."""
graph = defaultdict(list)
indegree = [0] * n
for a, b in edges:
graph[a].append(b)
indegree[b] += 1
q = deque(i for i in range(n) if indegree[i] == 0) # nothing left to wait for
order = []
while q:
node = q.popleft()
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return order if len(order) == n else [] # leftovers sit on a cycle
Time O(V + E), space O(V + E). If some nodes never reach indegree 0, they are waiting on each other in a cycle, so the order is shorter than n, and the answer to "can you finish?" is no.
The DFS version
DFS gives the same result: a node is finished once all of its dependents are finished, so reversing the finishing order gives a topological order. Cycle detection needs three states, because a node you are still exploring (grey) is different from one you already finished (black).
from collections import defaultdict
def topo_dfs(n, edges):
"""DFS version: post-order, reversed. Three colours detect a cycle (grey = on the current path)."""
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
out = []
def visit(u):
color[u] = GREY
for v in graph[u]:
if color[v] == GREY:
return False # back edge: cycle
if color[v] == WHITE and not visit(v):
return False
color[u] = BLACK
out.append(u) # all of u's dependents are done
return True
for u in range(n):
if color[u] == WHITE and not visit(u):
return []
return out[::-1]
Kahn's version is usually easier to get right under pressure, avoids recursion limits, and its level-by-level form answers "minimum number of semesters". Know that the DFS version exists and why it needs three colours.
Getting the edges right
![The pair [course, prereq] = [1, 0] becomes the edge 0 → 1, from prerequisite to course. Indegree counts how many things a node waits for; flipping the edges reverses the order.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/001-ea4caf93.png)
Most wrong answers come from building the graph backwards. Write one line on the whiteboard: "edge = prereq → course", and build from it.
Common bugs
- Reversed edges, from reading
[a, b]the wrong way round. - Missing isolated nodes: nodes with no edges must still be in the output. Loop over
range(n), not just the keys of the graph. - Two-state DFS cycle check: marking nodes only "visited" treats a node reached from two branches (a diamond) as a cycle. Use grey and black.
- Alien dictionary edge cases: compare only the first different letter of neighbouring words, and if a longer word comes before its own prefix (
"abc"before"ab"), there is no valid order. - Assuming the order is unique. Any valid order is accepted unless the question says otherwise. If it asks whether exactly one order exists, check that the queue never holds more than one node.
Say this in the interview
- "I build an indegree count. Anything at zero has no unmet prerequisites, so it can go next. If I can't output all n nodes, the rest form a cycle."
- "Each node and edge is handled once: O(V + E)."
Problems for this pattern
- Course Schedule: cycle check with Kahn's algorithm.
- Course Schedule II: return the order.
- Minimum Height Trees: peel leaves layer by layer, Kahn-style.
- Alien Dictionary: build the edges from neighbouring words.
- Longest Increasing Path in a Matrix: edges point to bigger neighbours; count Kahn layers (or DFS with a cache).
Related
Graphs · Graph BFS and DFS · Union-Find (cycles in undirected graphs) · Pattern Recognition Cheat Sheet