Strongly Connected Components
In short: a strongly connected component, or district, is a largest group of junctions where every one can reach every other along one-way streets. Collapse each district to a blob and keep only the streets between them, and you get a condensation with no loop — a dependency graph of districts. Kosaraju's finds every district in two DFS passes: record each junction's finish order, flip every street, then peel districts off in reverse finish order, each search landing in exactly one district because it starts in what is now a sink.
The old town on Meridian's east side is a maze of one-way streets. A driver who starts at the dock can loop round the fair and the gate and come back to the dock. Take the street from the gate up to the hill, though, and you can circle between the hill and the inn all day without ever finding a way back down to the dock.
Dispatch wants to group junctions into districts: groups where every junction can drive to every other and back. A van assigned to a district can then serve all of it without getting stranded outside. In graph terms, a district is a strongly connected component, or SCC. It's a largest set of nodes in which every node can reach every other along directed edges.
Reachability runs one way
In the graphs section, "connected" was symmetric: if Ana could reach Bo, Bo could reach Ana. One-way streets break that.
ahead = {"lane": ["dock"], "dock": ["fair"], "fair": ["dock"]}
def reach(start):
seen, todo = {start}, [start]
while todo:
j = todo.pop()
for nxt in ahead[j]:
if nxt not in seen:
seen.add(nxt)
todo.append(nxt)
return seen
print("dock" in reach("lane"), "lane" in reach("dock"))So "same district" means "reachable both ways". Testing that for every pair of junctions takes one search per junction, O(V × (V + E)), and it gets slow fast. Two classic algorithms find every district in linear time: Kosaraju's, which is easier to understand, and Tarjan's, which does it in a single pass.
Every graph is a DAG of districts
Draw each district as a single blob, and keep only the streets that go between districts. The result is called the condensation, and it never has a loop. If district A could reach B and B could reach A, every junction in both could reach every other, so they'd be one district. So the city is really a dependency graph of districts, just like the build schedule in the first lesson. Some districts are sources that nothing drives into, and some are sinks that nothing drives out of.
Kosaraju's algorithm uses this structure. If you start a search inside a sink district, it can't leave, so it collects exactly that district. The trouble is knowing where the sinks are before you've found the districts. Kosaraju's gets round that in two passes.
Kosaraju's: finish order, flip, peel
Pass 1. Run DFS over the whole graph and record each junction when it finishes. The junction that finishes last always lies in a source district.
Flip. Reverse every street. The districts don't change, since a round trip reversed is still a round trip, but every source district becomes a sink.
Pass 2. Go through junctions from last-finished to first. Each one not yet placed starts a search on the flipped streets. It's in a sink of the flipped graph, so the search collects its own district and nothing else. Then the next one does the same.
Watch the three stages on six junctions. Badges are finish numbers in pass 1, and district names in pass 2:
Kosaraju's in three moves. Record the finish order, flip every street, then peel districts off in reverse finish order.
Pass 1 runs DFS from dock. It goes dock, fair, gate, hill, inn, jetty, all the way down. 6 nodes, 7 edges, directed. At dock.
The first thing pass 1 finds out is where the last finisher is:
ahead = {"a": ["b"], "b": ["c"], "c": ["b", "d"], "d": []}
seen, finished = set(), []
for root in ["d", "c", "b", "a"]:
if root in seen:
continue
seen.add(root)
stack = [(root, iter(ahead[root]))]
while stack:
j, rest = stack[-1]
nxt = next(rest, None)
if nxt is None:
stack.pop()
finished.append(j)
elif nxt not in seen:
seen.add(nxt)
stack.append((nxt, iter(ahead[nxt])))
print(finished[-1])Here is Kosaraju's in Python. Both passes use explicit stacks, so a street map with thousands of junctions in a row can't hit the recursion limit:
Two DFS passes and one flip: O(V + E). Space is O(V + E) too: ahead and
behind each store every street once, and finished, seen and placed hold at
most one entry per junction.
The flip is the whole trick
Forget the flip and pass 2 runs downstream from a source district, swallowing everything it can reach:
Dock and fair form a two-way pair, and hill is a dead end, so there are two districts. This prints one district of all three. Fix the second pass.
Trace the finish order on a three-junction loop with a tail:
Tarjan's: one pass, with low-links
Tarjan's algorithm finds the same districts in a single DFS. Each junction gets a discovery number when DFS first reaches it, and a low-link, which is the smallest discovery number it can reach using its DFS subtree plus one step back to a junction still on the stack. Junctions go on a stack as they're discovered. When a junction finishes and its low-link equals its own discovery number, nothing below it can reach above it. It's the root of a district, and everything on the stack above it (itself included) is popped off as that district.
The badges below read discovery/low. Watch the low-links fall as back edges are
found, and a district pop off whenever a junction's two numbers match. Add the
street ("jetty", "gate") and run it again: jetty, hill and inn join the dock's
district, because now they can drive back.
Your Tarjan's. A district pops off the stack the moment a junction's low-link equals its own discovery number.
The recursive form reads well, but a production version needs to be iterative, like the explicit-stack DFS above, because a long street can go deeper than Python's recursion limit.
❓ Cross-question: "Kosaraju's or Tarjan's?" Both are O(V + E). Kosaraju's needs the flipped graph in memory and two passes, but each pass is an ordinary DFS you've already written. Tarjan's is one pass and uses less memory, and its low-link idea is exactly what the next lesson uses to find bridges.
Idioms & real-world patterns
Condense, then use the tools you already have
Once every junction carries a district number, the condensation is a DAG, and everything from the first lesson works on it. You can put districts in topological order, find the sources and sinks, or compute the longest chain. Two exercises below do exactly that. The trap districts are the sinks, and the capstone counts how many new streets make the whole city one district.
Where SCCs show up
A web crawler groups pages into clusters that link to each other. A compiler finds groups of mutually recursive functions. A package manager spots groups of modules that import each other, and a solver for boolean formulas with two variables per clause reduces the whole problem to SCCs of an implication graph. Each time, a tangle of directed links is simplified by collapsing its round-trip groups.
⚡ Advanced: one district, and nothing else
To check whether a whole graph is one district you don't need either algorithm. Search from any junction on the original streets, then from the same junction on the flipped streets. If both reach every junction, everything reaches it and it reaches everything, so all junctions reach each other. That's two BFS runs.
Quick practice
ahead = {"p": ["q"], "q": ["r"], "r": ["q"]}
def reach(start):
seen, todo = {start}, [start]
while todo:
j = todo.pop()
for nxt in ahead[j]:
if nxt not in seen:
seen.add(nxt)
todo.append(nxt)
return seen
print("p" in reach("q"), "q" in reach("p"))a, b, c form a district and d is its own, but this prints one big district of all four. Fix the order pass 2 walks `finished` in.
🎯 Your turn
Write districts(junctions, streets). Each [a, b] is a one-way street from a to
b. Return every district, meaning a largest group in which every junction reaches
every other, each sorted, and the list sorted. A junction nobody returns to is a
district of one.
districts(["a", "b", "c"], [["a", "b"], ["b", "a"], ["b", "c"]])→[["a", "b"], ["c"]]districts(["x", "y"], [])→[["x"], ["y"]]
Hint: Kosaraju's, meaning finish order, flip, then peel, with explicit stacks.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian is built. ✅