Ship what's unblocked,
merge what touches

Every dependency system you've ever cursed at — build tools, package managers, course catalogs, spreadsheet cells — is the same picture: nodes, plus directed edges where u → v reads "u must happen before v". If that picture has no directed cycle, it's a DAG — a directed acyclic graph — and a DAG always admits at least one topological order: a line-up of all the nodes where every arrow points forward. Usually many such line-ups; the interviewer will accept any of them.

Two things to internalize before any code:

• A topological order exists if and only if there is no cycle. One directed cycle and the whole thing is unschedulable: each member of the cycle politely waits for the previous one, forever. Deadlock. Most "can you finish?" problems are secretly just asking "is there a cycle?"
• The order is a property of the arrows, not the nodes. Nothing about a course called "CS201" makes it third; what makes it third is that its incoming arrows come from things you've already shipped. That framing — count incoming arrows — is the entire algorithm of Section 2.

The number of incoming edges of a node has a name, in-degree, and it deserves a friendlier one: it's the node's remaining-blockers counter. In-degree zero means "nothing is stopping you — go."

Here's the whole algorithm, in the words you'd use at a whiteboard: repeatedly ship anything with no remaining prerequisites. Shipping a node removes its outgoing arrows, which may unblock other nodes; queue those up and keep going. That's Kahn's algorithm — a to-do list that eats itself:

• Build an adjacency list (prereq → things it unlocks) and an indegree[] array in one pass over the pairs.
• Seed a queue with every node whose in-degree is 0 — they're buildable right now.
• Pop a node, append it to the order, and decrement the in-degree of everything it points at. Any neighbor that hits 0 joins the queue.
• When the queue empties, either you shipped everything (there's your order) or you didn't (Section 3).

Cost: O(V + E) — every node enters the queue once, every arrow gets decremented once; "touch each thing once" pricing. The queue is literally Chapter 15's BFS queue with a stricter bouncer: instead of "have I seen you?", admission is "has everything before you shipped?". Try it — take the eight courses below in any legal order you like, then flip the cycle on and watch the same clicking ritual jam.

Kahn's algorithm has the most elegant failure mode in the book: it just… stops early. If the queue empties while nodes remain, every leftover node has in-degree ≥ 1 — each one is waiting on another leftover. That's a cycle (or several), and your cycle test is one comparison: shipped == n. No colors, no recursion stacks, no cleverness. This single check is the whole answer to Course Schedule Medium, and appending each shipped node to a list upgrades it to Course Schedule II Medium — same loop, keep the receipts.

There is a DFS alternative, and it's worth one sentence in the room: mark nodes white/grey/black (unvisited / on the current recursion path / done), and a grey→grey edge is a back-edge, i.e. a cycle. It's the same recursion shape you drilled in Chapter 11, and post-order DFS reversed is also a valid topo order. Fine algorithm. But under interview pressure, three colors and a recursion stack offer more places to fumble than a queue and a counter — most people should say "I'll use Kahn's" and move on.

The hardest part of many topo-sort problems is noticing the graph at all. Alien Dictionary Hard is the canonical disguise: you get a list of words claimed to be sorted by some unknown alphabet, and you must recover the alphabet. No arrows anywhere in sight — until you remember what "sorted" means. If "ett" comes before "rftt", then at the first position where they differ, the earlier word's letter must come first in the alphabet: e → r. That's an edge.

So the solve is a pipeline: compare each adjacent pair of words (only adjacent — non-adjacent pairs add nothing new), extract one edge per pair from the first mismatch, then run plain Kahn's on the letters. If the topo sort deadlocks, the claimed dictionary contradicts itself. One edge case earns you real points: if a word is a strict prefix of the word before it ("apple" then "app"), no mismatch letter exists and no alphabet can fix it — return impossible before sorting anything.

Now drop the arrows. The second family of problems hands you undirected relations — "these two accounts share an email", "this wire joins these two houses" — and asks about groups: how many are there? Are these two in the same one? Which edge was one edge too many? You could answer with Chapter 15's DFS… once. But these problems typically stream their edges, asking questions as the graph grows, and re-flooding the whole graph per question is how an O(n) idea becomes an O(n²) submission.

Union-find (a.k.a. disjoint set union, DSU) is the tool built for exactly this. Its entire state is one array — parent[] — plus a helper. Every node points at some node in its group; follow the pointers up and you reach a node that points at itself. That's the root: the group's elected representative. The API is two functions:

• find(x) — follow parents up from x until a node is its own parent; return that root. Two nodes are connected iff their finds agree.
• union(a, b) — find both roots; if they differ, point one root at the other. Two groups just became one. If they're already equal, the edge you're adding connects a group to itself — remember that fact, it's a whole problem category (Section 7).

That's it. Start with parent[i] = i — n groups of one — and feed edges in. The component count starts at n and drops by exactly one on every successful union; no traversal ever happens. It's not a graph algorithm so much as group-membership bookkeeping.

The naive version has a lurking disaster: nothing stops the parent pointers from forming a chain. Union 0→1, 1→2, … 8→9 the lazy way and find(0) walks nine hops — the "tree" is a linked list, and finds cost O(n). Two one-line fixes make that impossible:

• Union by size (or rank): when merging, hang the smaller tree's root under the bigger tree's root. A node's depth now only grows when its whole tree gets absorbed by one at least as big — that can happen at most log n times. Trees stay bushy by law.
• Path compression: while find walks up, make every node it passes point (nearly) straight at the root. Each query leaves the structure flatter than it found it — the data structure is self-healing.

Together they push the amortized cost per operation to O(α(n)) — the inverse Ackermann function, a value that is ≤ 4 for any n that fits in this universe. Say "effectively constant" in the room and, if asked, name the function; that exchange is worth more than most solved problems. Build a worst-case chain below, then run one compressed find through it and watch it pancake.

Once the DSU exists, its canonical problems are almost embarrassingly short — each one is the machine plus a single observation:

• Number of Connected Components Medium — start the counter at n; every union that returns "merged" decrements it. Answer: the counter. (You could DFS this one — the graph is static — but the DSU version is five lines and no recursion.)
• Redundant Connection Medium — feed edges in order; the first edge whose two endpoints already share a root is the one closing a cycle. Return it. The "union returned false" branch is the answer.
• Graph Valid Tree Medium — a tree on n nodes is exactly: n − 1 edges and no edge ever redundant (equivalently: one component at the end). Two checks, both free once the DSU runs.
• Accounts Merge Medium — union accounts that share an email; each root collects its group. The interview twist is mapping strings to ids first — DSU over a dictionary of emails, not integers.

Outside the interview bank, this same machine is the heart of Kruskal's minimum-spanning-tree algorithm — sort edges by weight, union greedily, skip redundant ones. If a system-design-flavored interviewer asks where you'd use DSU "for real", that's your answer.

Part IV now holds three graph tools, and the problem statement tells you which one it wants before you've drawn anything:

• Directed edges meaning "before", and you need an order or a "can you finish" verdict → topological sort (this chapter). Cycle = impossible.
• Undirected edges meaning "same group", especially arriving over time → union-find (this chapter). Redundant union = cycle, for free.
• A frozen graph and a reachability/region question → Chapter 15's DFS/BFS. And the moment edges grow weights and the question says "cheapest", the BFS queue needs to become a priority queue — that's Dijkstra, one page-turn away in Chapter 17.

One symmetry worth saying out loud in an interview, because it sounds like mastery and is: both of this chapter's tools are cycle detectors — topo sort catches directed cycles (the queue starves), union-find catches undirected ones (the union comes back redundant). When Chapter 23's decision tree asks "does the problem smell like a cycle?", these are the two leaves it's choosing between.

The pattern, as a whiteboard skeleton:

1. 1Read the edges: directional "before/after" → topo sort. Symmetric "connected/merged" → union-find.
2. 2Topo: one pass over the pairs builds adj[prereq] → courses and indegree[] — say the arrow direction out loud.
3. 3Queue every node with in-degree 0; they're buildable now.
4. 4Loop: pop, record, decrement each neighbor; any neighbor hitting 0 joins the queue.
5. 5Recorded < n? Cycle → return impossible. Otherwise the record is your order.
6. 6DSU: parent[i] = i, size[i] = 1; find walks to the root, compressing as it goes.
7. 7union hangs the smaller root under the bigger; roots already equal → redundant edge / cycle detected.
8. 8Components = n − successful unions; valid tree = n − 1 edges and zero redundant ones.

Course Schedule Medium first: given numCourses and pairs [course, prereq], can you take everything? It's Kahn's algorithm verbatim — build, seed, drain, compare the count. Then the chapter's other half: the complete DSU with path compression and union by size, the twelve lines you'll reuse across the entire connectivity family. Read the Python for the shape and flip to Scala to see the same two machines with types on.