← All patterns
Topological Sort
Linear ordering of a DAG respecting dependencies. Kahn's BFS for indegree-based ordering; DFS post-order for the reverse. Cycle detection comes for free.
11 problems
1 Easy 5 Medium 5 Hard
Linear ordering of a DAG such that every edge `u → v` puts `u` before `v`. Kahn's algorithm uses BFS with indegrees: enqueue 0-indegree nodes, process and decrement neighbors. DFS post-order gives the reverse topological order. Cycle detection is automatic — if not all nodes are emitted, a cycle exists.
Variants include 'critical path' (DP over the topological order) and 'parallel scheduling' (layered BFS where each level is a parallel batch).
When to reach for this pattern
- Dependencies / prerequisites / build order
- Course schedule, package compile order, makefile-style flow
- Need to detect cycles in a directed graph
- Find the longest path in a DAG (critical path)
Canonical template
// Kahn's BFS
queue<int> q;
for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
return (int)order.size() == n ? order : vector<int>{};C++ · adapt the names and types to your problem.
Common pitfalls
- Building the graph with the wrong edge direction (prereq → course vs course → prereq)
- Not initializing indegrees from edges
- Returning a partial order when the graph has a cycle — always validate length
- Forgetting to handle disconnected components — Kahn's handles them automatically; DFS needs an outer loop
Related patterns
Problems (11)
- Hard
- Medium
- Medium
- Easy
- Medium
- Medium
- Hard
- Hard
- Hard
- Medium
- Hard