Topological Sort · bigonotes

Topological sort puts the nodes of a directed graph in an order where every edge points forward: each task comes after everything it depends on. You can't put on shoes before socks. It only exists for a DAG (directed acyclic graph), so the same algorithm doubles as a directed cycle check.

The idea#

Think of a to-do list. A task with in-degree 0 (no incoming edges, so no unfinished prerequisites) can be done right now. That is Kahn's algorithm:

Count each node's in-degree.
Put every node with in-degree 0, and only those, in a queue.
Pop a task and append it to the order. "Crossing it off" lowers the in-degree of each task that depended on it.
When a task's in-degree hits 0, it is unlocked: add it to the queue.
Repeat until the queue is empty.

Why it works: a node enters the order only after all of its prerequisites are in it. So every edge points forward in the final order.

If the order ends up shorter than the number of nodes, some nodes never reached in-degree 0. They are waiting on each other in a cycle, so no valid order exists.

How to spot it#

Topological sort is the tool for dependency resolution. Look for these signals.

"Prerequisites" / "dependencies": Course Schedule, build order ("library A depends on library B").
"Find a valid ordering" under constraints: Alien Dictionary.
Cycle detection in a directed graph: if you can't process every node, there is a cycle (a deadlock).
Parallel planning: "minimum time / semesters to finish everything", where every task with in-degree 0 can run at the same time.

Template#

This is Kahn's algorithm. The edge direction is the usual bug, so the template writes it out. An edge goes from the prerequisite to the task that needs it.

for each (task, prereq) pair:
    add edge prereq -> task          # direction matters
    in_degree[task] += 1
queue = every node with in_degree 0
order = empty list
while queue is not empty:
    node = pop from the front of queue
    append node to order
    for each next in neighbors of node:
        in_degree[next] -= 1
        if in_degree[next] == 0:     # last prerequisite just finished
            push next onto queue
if length of order < number of nodes:
    there is a cycle: no valid order
return order

Building the graph is $O(E)$ , and the loop handles every node and edge once, so the whole thing is $O(V + E)$ .

DFS alternative: post-order, then reverse#

You can also get a topological order from DFS. Record each node at its exit, after you explore all of its neighbors. By then everything that must come after it is already in the list. So the list is in reverse order, and you flip it at the end.

Here is a trace with one dependency, Tie → Jacket (the tie goes on first):

Step	Event	List
1	Enter `Tie`, see neighbor `Jacket`	`[]`
2	Enter `Jacket`; it has no outgoing edges	`[]`
3	Exit `Jacket`	`['Jacket']`
4	Back in `Tie`; exit `Tie`	`['Jacket', 'Tie']`
5	Reverse	`['Tie', 'Jacket']`

The trace has no cycle, but real input might. So the full DFS keeps two sets: on_path for nodes on the current path, and done for finished nodes.

dfs(node):
    if node in on_path: report a cycle
    if node in done: return
    add node to on_path
    for each next in neighbors of node:
        dfs(next)
    remove node from on_path
    add node to done
    append node to post          # record at exit
run dfs from every node
return post reversed

The on_path set is the same back-edge check as in Cycle Detection. Without it, a cyclic graph still returns an order, but a wrong one.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Starting the queue with anything other than in-degree 0 nodes. "Doable now" means no remaining prerequisites.
Reversing the edge direction (task → prereq), which produces the order backwards.
Forgetting the length check, so a cyclic input returns a partial order.
Counting a duplicate edge twice in the in-degree. That node then never reaches 0.
Leaving out nodes that have no edges. They still belong in the order.
DFS version: forgetting the final reverse.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the two Course Schedule problems.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Course Schedule

You only need a yes or no. Run Kahn's algorithm and check whether the order holds all n courses.

Hint: Course Schedule II

Return the order itself, or an empty list when there is a cycle. Check the edge direction: it goes from the prerequisite to the course.

Hint: Alien Dictionary

Compare each pair of adjacent words. The first position where they differ gives one edge (word1[j] → word2[j]); later positions say nothing. If a longer word comes before its own prefix ("abc" before "ab"), no order can work, so return "". Add every letter as a node, and keep a set of neighbors so the same edge does not count twice.

Hint: Alien Dictionary: complexity

The graph has at most 26 nodes and $26^2$ edges. So the total cost is $O(C)$ for $C$ characters across all words.

Hint: Parallel Courses

Process the queue level by level. Everything in the queue right now is one semester; the tasks it unlocks form the next. The number of levels is the answer. The same idea fits "minimum time to finish all tasks".

Hint: Build a Matrix with Conditions

The row constraints and the column constraints do not affect each other. Treat them as two separate topological sorts.

Hint: Minimum Height Trees

Trim leaves layer by layer until 1 or 2 nodes remain. This is Kahn's algorithm on an undirected tree, with degree 1 in the role of in-degree 0.

Hint: Course Schedule IV

This is a reachability question: "is A a prerequisite of B?" Answer it with DFS reachability or Floyd-Warshall (an all-pairs algorithm, used here for reachability).

Hint: Longest Increasing Path in a Matrix

Draw edges from smaller to larger cells. The grid is then a DAG. DFS with memoization or a topological order both work.

Key takeaways#

Only in-degree 0 nodes are ready; finishing one may unlock others.
Edges point from prerequisite to dependent.
An order shorter than $n$ means a cycle.
DFS gives the same result: record nodes at exit, then reverse.
Process the queue level by level when the question asks for rounds or semesters.

Core idea#

Topological sort orders the nodes of a directed graph so every edge points forward. It exists only for a DAG, so the same pass also detects a directed cycle.

Key points#

Kahn's algorithm: queue every node with in-degree 0, and only those.
Pop a node and append it to the order. Lower the in-degree of each dependent.
A dependent whose in-degree hits 0 joins the queue.
An order shorter than n means a cycle.
Edges point from prerequisite to dependent: graph[pre].append(course).
DFS alternative: record each node at exit, then reverse the list. Keep the on_path check for cycles.
Time is $O(V + E)$ .
Spot it: prerequisites, dependencies, build order, a valid ordering under constraints.

Variations#

Problem	Twist
Course Schedule I / II	Return `len(order) == n`, or the order
Parallel Courses	Process the queue level by level; levels are semesters
Alien Dictionary	First differing letter of adjacent words gives one edge
Minimum Height Trees	Trim degree-1 leaves until 1 or 2 nodes remain
Build a Matrix with Conditions	Two separate topological sorts

Template#

for each (task, prereq) pair:
    add edge prereq -> task          # direction matters
    in_degree[task] += 1
queue = every node with in_degree 0
order = empty list
while queue is not empty:
    node = pop from the front; append node to order
    for each next in neighbors of node:
        in_degree[next] -= 1
        if in_degree[next] == 0: push next onto queue
return order if length of order == n, else no order (cycle)

Pitfalls#

Reversing the edge direction. The order comes out backwards.
Forgetting the length check. A cyclic input returns a partial order.
Counting a duplicate edge twice in the in-degree. Use a set of neighbors.
Alien Dictionary: a longer word before its own prefix ("abc" before "ab") means return "". Add every letter as a node.
DFS version: forgetting the final reverse.

Say it in an interview#

"Only in-degree 0 nodes are ready. Finishing one may unlock others."
"If the order is shorter than n, the rest are stuck in a cycle."