Order nodes so every edge points forward — the answer to 'what can I do first?'
The tell: Prerequisites, build order, task scheduling, or any DAG where order matters.
Reach for it when
Course schedule / build dependency order
Detecting a cycle in a directed graph
Longest path in a DAG (process in topological order)
Alien dictionary letter ordering
Reference implementation
topo_order — Kahn's algorithm
from collections import deque
def topo_order(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""edges are (before, after). Returns [] if a cycle makes ordering impossible."""
graph: list[list[int]] = [[] for _ in range(n)]
indegree = [0] * n
for before, after in edges:
graph[before].append(after)
indegree[after] += 1
queue = deque(node for node in range(n) if indegree[node] == 0)
order: list[int] = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == n else []
Complexity: O(V + E) time, O(V) space.
What goes wrong
Building the edge direction backwards — (prerequisite, course) vs (course, prerequisite).
Forgetting that a short result means a cycle, and returning a partial order as if it were valid.
Decrementing indegree more than once for parallel duplicate edges when the problem forbids them.