STEP 15 · GRAPHS · TOPOLOGICAL ORDER IS THE SCHEDULE · MEDIUM

Course Schedule I / II

WHAT IT SAYS

Given courses and prerequisite pairs, decide whether all courses can be finished (I), and produce a valid order to take them (II).

WHAT IT'S REALLY ASKING

"Play the eager student: any course with ZERO unmet prerequisites can be taken right now — taking it can never hurt, only unlock. Take one, cross it off everyone's prerequisite lists, repeat. Either the crossing-off cascades through every course, or it stalls — and a stall means some group of courses are all waiting on each other, which is a cycle, which no schedule of any kind can satisfy."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Search over orderings

Exponential — the ordering space is factorial, the backtrack tree enormous

Try to build a schedule by picking courses one at a time, backtracking whenever a picked course turns out to have an untaken prerequisite; or check permutations against the constraint list until one satisfies all pairs.

WHERE THE WORK IS WASTED — Backtracking presumes early picks can be wrong in ways only later context reveals — but here a course whose prerequisites are all met is NEVER a wrong pick. Exchange argument: take any valid schedule that doesn't start with available course c; c's prerequisites are met from the start, so sliding c to the front reorders nothing it depends on and delays nothing that depends on it having been later — still valid. So every available course is a safe first move, no alternative ever needs exploring, and the entire backtrack tree collapses to a single greedy line. The exponential search is exploring choices that provably don't exist.

KEY OBSERVATION — THE UNLOCKlink

Zero unmet prerequisites is always a safe move — greedily peel.

Model first: courses are vertices, each prerequisite pair (a requires b) a directed edge b → a. A valid schedule is an ordering where every edge points forward — which is the DEFINITION of a topological order. So question I is 'does a topological order exist?' (⟺ the graph is acyclic), and question II is 'produce one'. The reduction is the real test of this problem; the algorithm afterward is standard. Now the algorithm, and notice how the story writes it. A vertex's IN-DEGREE is exactly 'how many prerequisites are still unmet'. In-degree zero means takeable now — and by the exchange argument above, taking it is always safe: greedy needs no lookahead because no available choice can ever foreclose another. Taking a course removes its outgoing edges — decrement each dependent's in-degree — possibly unlocking new zeros, which join the queue. This is Kahn's algorithm, but derived as a simulation of the eager student rather than recalled as a named procedure. Why must a DAG always offer a zero? Walk edges backward from any vertex; the graph is finite, so either you find a source (in-degree zero) or you revisit a vertex — and a backward revisit is a cycle. Contrapositive: acyclic guarantees the peeling never stalls with vertices remaining. And when peeling DOES stall, the leftovers certify a cycle: every remaining vertex has an unmet prerequisite among the remaining — each waits on another, and following the waiting relation through a finite set must loop. So one process answers both questions at once: the pop-order IS the schedule (II), and popping all V vertices IS the feasibility verdict (I). Fewer than V popped: return false, or empty. One degree of freedom worth naming: when several courses are simultaneously available, ANY may go next — the queue could be a stack, a heap, anything, and feasibility is unaffected. That slack is where follow-ups live ('lexicographically smallest schedule' → replace the queue with a min-heap), and recognising the slack is recognising that topological orders are generally plural.

Kahn: in-degrees, queue the zeros, pop and unlock

O(V + E) time — each edge decremented once — O(V + E) space for the graph

Build adjacency lists and in-degree counts from the prerequisite pairs. Enqueue every zero-in-degree course. Loop: pop a course, append it to the order, decrement each dependent's in-degree, enqueueing any that reach zero. Popped count equals V: the order is the answer (or 'true' for I). Otherwise: cycle — return false or empty. (DFS alternative: three-colour cycle check, and the REVERSE of postorder finishing times is a topological order.)

WHAT YOU TRADED — Kahn is iterative, yields the order in construction sequence, and detects the cycle as leftover count — but names no specific cycle; DFS finishing-time order exposes the actual back edge on failure, at recursion-depth risk. Both are linear; choose by deliverable. The transferable lesson: 'dependencies must come first' is ALWAYS a DAG plus topological sort — build order, task scheduling, formula evaluation, import resolution — and the greedy peel is safe precisely because an unlocked move can never become wrong.

WATCH THE IDEA RUN

SCHEDULE

—

ready queue (in-degree 0) —

taken 0 / 6

Give every course a count of its UNMET prerequisites — its in-degree. Nothing else about the graph matters yet.

step 1 / 15

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Peel the Unblocked

YOU'LL SEE IT AGAIN WHEN

Items with 'X before Y' constraints, asked for feasibility or an explicit ordering — topological sort wearing a costume.
An element with no unmet constraints is a provably safe next move (exchange argument), so greedy replaces search entirely.
The process stalling with items remaining is itself the infeasibility certificate — mutual waiting is a cycle.

SAME BLUEPRINT, DIFFERENT PROBLEM

Detect Cycle in a Directed Graph (the verdict without the order)Alien Dictionary (topo sort where the edges must be mined first)Minimum Height Trees (peeling leaves instead of sources)Parallel Courses (peeling in level batches = semesters)

The bar isn't "solved it once." It's "could rebuild it from the observation."