Topological Sort
Repeatedly take nodes with zero remaining prerequisites. If you cannot empty the graph there is a cycle.
GraphsO(V + E)New5 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
course schedule
build order
dependencies
detect cycle in a directed graph
The template
Get this into muscle memory, then adapt the condition per problem.
const q = nodes.filter((u) => indeg[u] === 0);
const order: number[] = [];
while (q.length) {
const u = q.shift()!;
order.push(u);
for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
}
return order.length === V ? order : []; Watch Topological Sort (Kahn)If you are stuck
The generic hint ladder for this pattern, in order.
- 1Prerequisites define a directed edge, so the question is about ordering.
- 2Track how many unmet prerequisites each node still has.
- 3If the produced order is shorter than the node count, a cycle blocked it.
Drill it
Every problem in the bank that uses this pattern.
0 / 5 solved