Topological Sort

What is this?

You have a list of tasks and a pile of "X must happen before Y" rules. A valid order is one where nothing starts before its prerequisites finish. The algorithm mirrors how a person would do it: find everything with no outstanding prerequisites, do it, cross it off other tasks' lists, and repeat.

Two useful things fall out for free. If you ever run out of ready tasks while work remains, the remaining tasks depend on each other — a cycle. And if you drain the ready set one whole batch at a time, the number of batches is the minimum number of rounds needed when unlimited work can happen in parallel.

💡 Fun fact: Parallel Courses asks not for an order but for the number of semesters — which is the longest path in the DAG, and Kahn's algorithm gives it with a one-line change. Instead of popping one node at a time, capture the queue's size and drain exactly that many; each round is a semester. It is the same level-batching trick as BFS on trees, and it is how project-management tools compute a critical path.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: repeatedly take everything with no remaining prerequisites. Count nodes and you get an order; count rounds and you get the minimum time under unlimited parallelism; count neither and run out early and you have found a cycle.

1. Kahn's algorithm, and the free cycle check

from collections import deque

indeg = [0] * n
for u in range(n):
    for v in adj[u]:
        indeg[v] += 1

queue = deque(i for i in range(n) if indeg[i] == 0)
order = []
while queue:
    u = queue.popleft()
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            queue.append(v)

if len(order) < n:
    return "cycle detected"      # some nodes never reached in-degree 0

The final check is the whole cycle detection. Nodes inside a cycle can never have their in-degree fall to zero — each is waiting on another member of the same cycle — so they are never emitted. No separate colouring pass, no recursion stack.

2. Counting rounds instead of nodes

semesters = 0
while queue:
    semesters += 1
    for _ in range(len(queue)):      # freeze the size: this batch is one semester
        u = queue.popleft()
        ...

Freezing len(queue) before draining is the same discipline as level-order BFS, and it is exactly what turns "in what order" into "in how many rounds".

3. When the order is over edges, not nodes

Reconstruct Itinerary is the odd one in this chapter. It asks for a path using every ticket exactly once — an Eulerian path, not a topological order — with the extra requirement that ties break lexicographically. Hierholzer's algorithm solves it: walk greedily to the smallest unused destination until stuck, then unwind, appending each stranded airport to a result list which is reversed at the end.

The reason a node only lands in the result once it is stuck is subtle and worth stating: getting stuck means all its edges are used, so it must appear after everything reachable from it — which is precisely the reversed post-order.

4. A 30-second worked example (Parallel Courses)

Prerequisites 1→3, 2→3, 3→4:

in-degrees:  1:0   2:0   3:2   4:1
queue = [1, 2]

semester 1 — drain 2 nodes: take 1 and 2
             3's in-degree: 2 → 1 → 0   → enqueue 3
             queue = [3]
semester 2 — drain 1 node: take 3
             4's in-degree: 1 → 0       → enqueue 4
             queue = [4]
semester 3 — drain 1 node: take 4
                                          answer = 3 semesters

Courses 1 and 2 were taken together because nothing forces them apart — which is exactly what "unlimited parallelism" means, and why counting rounds rather than nodes gives 3 instead of 4.

5. Where you'll actually meet this

• Build systems. make, Bazel and every package manager topologically sort targets, and report a cycle when the sort fails.
• Spreadsheet recalculation. Cell formulas form a DAG; circular-reference errors are precisely the len(order) < n check.
• Database migrations. Applying schema changes in dependency order, and detecting a cyclic dependency between them.
• Course and project planning. The semester count is the critical path — the minimum duration regardless of resources.
• Task orchestration. Airflow-style DAG schedulers use the level batching to decide what can run concurrently.

6. Problems in this chapter

▶ Reconstruct Itinerary

Use every ticket exactly once, starting at JFK, choosing the lexicographically smallest itinerary. Hierholzer's algorithm with a sorted adjacency structure; append on getting stuck and reverse at the end.
Pattern: Eulerian path (Hierholzer). Target: O(E log E) for the sorting, O(E) for the walk.

▶ Parallel Courses

Minimum semesters to finish all courses under unlimited parallelism, or -1 if the prerequisites are cyclic. Kahn's algorithm counting rounds instead of nodes.
Pattern: level-batched topological sort. Target: O(V + E) time, O(V) space.

7. Common pitfalls 🚫

• Skipping the cycle check. Without comparing emitted count to n, a cyclic input silently returns a partial order.
• Not freezing the queue size. Nodes enqueued mid-round get counted in the current semester, undercounting the answer.
• Building in-degrees from the wrong direction. An edge u → v increments v, not u; reversing it produces a valid-looking but wrong order.
• Sorting destinations inside the loop in the itinerary problem. Sort once up front, or use a heap.
• Appending airports when visited rather than when stuck. Hierholzer's correctness depends on the post-order append and the final reverse.
• Assuming the topological order is unique. Usually many are valid; if the problem wants a specific one (lexicographically smallest, say), use a heap instead of a plain queue.
• Returning 0 for an empty graph where the problem expects otherwise — check what "no courses" should produce.

8. Key takeaways

1. Take everything with no remaining prerequisites, repeatedly. That sentence is the algorithm.
2. Cycle detection is free — if fewer than n nodes were emitted, the rest are in a cycle.
3. Count rounds, not nodes, when the question is "how long" rather than "in what order".
4. Freeze the queue size to keep rounds separate.
5. A specific ordering needs a heap, not a queue.
6. Eulerian is not topological. "Use every edge" is a different problem with a different algorithm.
7. Why interviewers like it: dependency resolution is universal, and the two extensions — cycle detection and round counting — test whether you understand the algorithm or merely recall it.

Order: Parallel Courses → Reconstruct Itinerary.

Course Schedule, the cycle-detection warm-up this chapter assumes, is in Coding Interview 101.