Finding the Cycle
In short: colour every depot white, grey or black as DFS runs: grey means "on the path you're walking right now", black means "finished, nothing below it can lead back to you". An arrow into a grey depot is a back edge, and it closes a loop — the loop is exactly the grey path from that depot down to where you stand. An arrow into a black depot never is a loop, because anything reachable from a black depot was already explored while it was still grey.
When a Meridian depot fills up, it forwards its overflow to another depot. Each depot manager sets their own rule, and nobody looks at all of them together. So one night north forwards to east, east forwards to south, south forwards back to north, and a van of parcels drives in a circle until morning.
Kahn's algorithm from the last lesson could tell you that some loop exists, because loops are what it leaves behind. The operations team wants more than that: which depots, in what order, so someone can phone the right manager. This lesson finds the loop itself, using depth-first search and three colours.
Visited is not enough
The first idea is to run DFS and shout "loop!" the moment you reach a depot you've already visited. Try it on four depots where two routes happen to meet:
after = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
visited = set()
def visit(depot):
if depot in visited:
return True # "seen it before, must be a loop"
visited.add(depot)
return any(visit(nxt) for nxt in after[depot])
print(visit("a"))Reaching an old depot tells you two routes meet. It doesn't tell you there's a way back. For that you need to know whether the old depot is still on the path you are walking right now.
Three colours
Give every depot one of three colours:
- white: not visited yet;
- grey: visited, and still on the current DFS path, because we are somewhere underneath it;
- black: finished, meaning everything reachable from it has been explored.
A depot turns grey when DFS enters it and black when DFS leaves it. The grey depots always form a single path from the root to where you're standing. Now the rule is exact:
An edge into a grey depot is a back edge, and it closes a loop: the grey path runs from that depot down to you, and the edge leads back up to it. An edge into a black depot is never a loop, because if anything reachable from it led back to you, DFS would have found that while it was still grey.
Here it is on a small slice of the city. Grey depots are highlighted and badged, black ones are finished:
Only an edge back into a grey depot is a loop. The grey depots on screen are the loop's candidates, in path order.
Start at hub. Grey means it is on the current path and not finished. 5 nodes, 6 edges, directed. At hub. Frontier: hub. hub: grey.
The last frame is the whole trick. The loop is the part of the grey path from the depot you hit to the depot you're on. If you keep the grey path in a list, and an iterative DFS already does, reading the loop off takes one slice:
path = ["hub", "north", "east", "south"]
back_edge = ("south", "north")
print(path[path.index(back_edge[1]):])An iterative three-colour DFS
A recursive DFS would work, but a long chain of depots can have thousands of
levels and Python's default recursion limit is about 1,000. The explicit version keeps
a stack of (depot, iterator over its rules). The iterator remembers how far
through that depot's rules we've got, which is what a recursive call's local loop
would have remembered:
Every depot changes colour at most twice and every rule is followed once, so this is
O(V + E), the same as the DFS it's built from. A depot that forwards to itself
is handled for free: it is grey when its own rule is examined. Space is O(V + E)
too: the colour map and the explicit stack hold at most one entry per depot, and
sends holds every rule once.
Step through the colours on a three-depot loop:
Two-way roads are different
Meridian's roads mostly run both ways, and an undirected graph needs a different
test. In an adjacency list, every two-way road a–b appears twice, once as b in
a's list and once as a in b's. So the moment DFS walks from a to b, b
sees a as a visited neighbour. That's just the road you arrived on, and it
isn't a ring. This checker misses that:
A straight line of three junctions has no ring, but this prints True for it. Fix has_ring so the road you arrived on doesn't count, and a real triangle is still caught.
In an undirected graph there are no one-way traps like the diamond, so any visited neighbour other than your parent really does mean a ring. There's also the union-find test from the graphs section: add roads one by one, and the first road whose two ends already share a root closes a ring. It is the drill exercise below.
❓ Cross-question: "Why doesn't union-find work for one-way rules?" Union-find only knows "connected", not "in which direction". The diamond's four rules connect all four depots into one group, and the fourth rule joins two depots already in the same group, yet there is no directed loop. Direction is exactly the information union-find throws away.
Your turn to drive it
Here's the three-colour DFS on the forwarding rules, badging each depot with its
colour and marking the back edge in red when it appears. Delete the rule
["south", "north"] and run it again: every depot should finish black with no
error. Then add ["yard", "hub"] and find out which loop it reports.
Your three-colour DFS. The grey depots are always one path, and a loop is an arrow from the bottom of that path back into it.
Idioms & real-world patterns
Where loops hide in real systems
The same check guards a lot of production software. Build systems refuse circular targets, spreadsheets refuse a cell that refers to itself through other cells, package managers refuse circular dependencies, and databases look for deadlocks where transaction A waits for B and B waits for A. That last one is exactly Meridian's forwarding loop: each edge means "is waiting for".
Rotate before you compare
A loop has no natural first element, so north, east, south and east, south, north are the same loop. Before storing, comparing or testing loops, rotate each
to start at its smallest member, and for two-way rings choose a direction too. The
main task and the capstone exercise both ask for this.
⚡ Advanced: which edges are which
DFS sorts every directed edge into one of four kinds: tree edges (into white), back edges (into grey), and forward or cross edges (both into black). A directed graph has a loop exactly when some DFS finds a back edge. The next two lessons use the same classification: strongly connected components are built out of back edges, and bridges are the tree edges that no back edge spans.
Quick practice
sends = {"p": ["q"], "q": ["r"], "r": []}
colour = {d: "white" for d in sends}
found = False
def visit(d):
global found
colour[d] = "grey"
for nxt in sends[d]:
if colour[nxt] == "grey":
found = True
elif colour[nxt] == "white":
visit(nxt)
colour[d] = "black"
visit("p")
print(found)a, b, c, d form a diamond with no loop, but this prints True. d is reached once as black and once more as a false "loop". Fix the colour test.
🎯 Your turn
Write find_loop(depots, forwards). Each [a, b] rule forwards overflow from a
to b. Return a loop as a list of depots in forwarding order, rotated to start at
its alphabetically smallest depot, or [] if parcels can never circle. Each test
has at most one loop.
find_loop(["a", "b", "c"], [["b", "c"], ["c", "a"], ["a", "b"]])→["a", "b", "c"]find_loop(["a", "b", "c", "d"], [["a", "b"], ["a", "c"], ["b", "d"], ["c", "d"]])→[]
Hint: the iterative three-colour DFS above, plus
i = loop.index(min(loop)) and loop[i:] + loop[:i].
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. ✅