Topological sort
Some jobs have to happen before others. Give every job a count of the prerequisites it is still waiting for, and start a job the moment its count reaches zero.
Problems worked on this page, and more to practise
- 207. Course Schedule
- 210. Course Schedule II
- 2115. Find All Possible Recipes from Given Supplies
- 802. Find Eventual Safe States
- 851. Loud and Rich
- 310. Minimum Height Trees
- 1462. Course Schedule IV
- 1136. Parallel Courses
- 444. Sequence Reconstruction
- 269. Alien Dictionary
- 2050. Parallel Courses III
- 329. Longest Increasing Path in a Matrix
- 1203. Sort Items by Groups Respecting Dependencies
When should I use a topological sort?
When the input is a set of items plus rules of the form “this one has to come before that one”, and you are asked for an order that respects every rule, or asked whether one exists at all. Course Schedule, build systems, task scheduling and dependency resolution all have that shape. The rules have to be directed: if the relation is symmetric, such as “these two are in the same group”, the question is about connected pieces and belongs to union-find or a plain graph walk instead.
What is the difference between Kahn’s algorithm and the DFS version?
Kahn’s keeps a count per item of how many prerequisites are still unfinished, and drains a queue of the items whose count is zero. The DFS version walks the graph and appends each item after everything it points at, then reverses the list. Both are O(V + E) and both detect a cycle. Kahn’s is easier to get right under pressure and gives the cycle check as a length comparison; the DFS version is shorter if you already have a recursive walk on the page.
How does a topological sort detect a cycle?
With Kahn’s, items on a cycle wait for each other, so none of their counts ever reaches zero, so none of them ever enters the queue or the output. Compare the length of the output with the number of items: if it is short, the missing items are exactly the ones on or behind a cycle. With the DFS version, you keep three states per node and a cycle is an arrow into a node that is still on the recursion stack.
Which way does the edge point in Course Schedule?
The input pair [a, b] means you must take b before a, so the arrow runs from b to a: finishing b is what releases a. The in-degree belongs to a, the course that owes the prerequisite. Reading the pair the other way round still passes Course Schedule, because reversing a graph never creates or removes a cycle, and it fails Course Schedule II, which returns the order upside down.
Is the topological order unique?
Almost never. Any item whose prerequisites are all done can go next, so a graph with several ready items has several valid orders, and Kahn’s and the DFS version usually disagree. LeetCode accepts any valid order. If the interviewer asks for the lexicographically smallest one, replace the queue with a min-heap and pop the smallest ready item each time, which costs O((V + E) log V).