The idea
A topological order lists the vertices of a directed graph so that for every edge u → v, u comes before v. It exists exactly when the graph has no cycle (a DAG).
Kahn’s algorithm: count incoming edges for every vertex, repeatedly take a vertex with none, and remove its outgoing edges. If fewer than n vertices come out, there is a cycle.
Processing vertices in topological order is how dynamic programming runs on a DAG, for example the longest path.
Sample problem
210. Course Schedule II ↗ Medium
There are n courses. A pair [a, b] means course b must be taken before course a. Return an order in which all courses can be taken, or an empty list if it is impossible.
numCourses = 5, prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3]] output = [0,1,2,3,4]
Why the solution works
The courses and prerequisites form a directed graph, and a valid order is a topological order: every edge points forward.
A course with no unfinished prerequisite is always safe to take next. Taking it removes its outgoing edges, which may free other courses. Kahn’s algorithm repeats this with a queue.
If the prerequisites contain a cycle, the courses on it wait for each other forever, the queue runs dry early, and fewer than n courses are output. That is how impossibility is detected.
Complexity: O(V + E) time and memory.
Watch out
- Detect cycles by comparing the size of the order with n.
- Many orders can be valid; if the problem wants the smallest one, use a priority queue instead of a queue.
- For DP on a DAG, relax edges in this order so every source value is final when used.