Topological Sort

A topological order lists the vertices of a directed acyclic graph so every edge points forward. Kahn's algorithm builds one with a queue of vertices whose indegree is zero, popping one at a time and lowering the indegree of each neighbor so a vertex enters the queue only after its last prerequisite finishes.

Variant	Ready set	Typical use
Kahn's with a queue	Plain FIFO	Any valid order, cycle check
Kahn's with a min-heap	Smallest ready vertex first	Lexicographically smallest order
DFS post-order, reversed	The recursion stack	Same order, cycle found via a grey mark

Cycle detection comes free. If fewer than $n$ vertices ever pop from the queue, the remaining vertices sit on or behind a cycle, each waiting on another forever. Topological order is also the natural fill order for dynamic programming on a DAG, because by the time a vertex pops, every predecessor has already computed its answer, so counting paths or finding the longest chain takes one update per edge.

Approach	Time	Extra space
Rescan for a ready vertex each round	$O(n \cdot m)$	$O(n)$
Kahn's with a queue	$O(n + m)$	$O(n + m)$
Kahn's with a min-heap	$O((n + m) \log n)$	$O(n + m)$

Use it whenever a problem gives you prerequisites between courses, build steps, or tasks, and asks whether they can all finish, in what order, in how many ways, or how long the critical chain takes.

The problems below start with counting indegrees to identify a single source, move through Kahn's cycle check, lexicographically smallest ordering with a min-heap, path counting, and critical-path duration, and end with deriving the dependency edges from sorted words before ordering the alphabet.