Capstone: Meridian's Network Model
In short: one sorted union-find pass answers two questions — how many pieces the network falls into, and what the cheapest backbone linking each piece costs — because Kruskal's algorithm is that pass, just with the roads sorted first. One low-link DFS over the same roads then answers two more: every critical road (a bridge) and every critical junction (an articulation point). Four numbers, one sort, one union-find pass and one DFS.
Meridian's planners want one page about the road network before anything gets routed over it. Is the city one piece, or are there parts no van can reach? What would the cheapest backbone cost, the fibre that keeps every depot talking? And where are the weak points, the roads and junctions whose closure would split the city?
Every answer is something you've already built in this section. The capstone puts
them together into one function, network_report, and shows that one union-find
pass and one depth-first search are enough for all four numbers.
Part 1: pieces and the backbone, in one pass
A road network can be in several pieces: a new estate whose access road isn't finished, or an island reached only by ferry. Counting pieces is union-find: start with one piece per junction, and every road that joins two different groups leaves one fewer.
junctions = ["a", "b", "c", "d", "e", "f"]
roads = [("a", "b"), ("c", "d"), ("d", "e"), ("e", "c")]
parent = {j: j for j in junctions}
def find(x):
while parent[x] != x:
x = parent[x]
return x
pieces = len(junctions)
for a, b in roads:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
pieces -= 1
print(pieces)Now look at what that loop is doing. It's Kruskal's algorithm without the sort. Sort the roads by cost first and the same unions build the cheapest backbone. On a network in several pieces, Kruskal's never finds a road between them and simply returns one tree per piece, a minimum spanning forest. So one pass gives two answers: pieces is junctions minus successful unions, and the backbone cost is the sum of their costs.
The backbone isn't always the cheap roads, though:
roads = [("a", "b", 1), ("b", "c", 2), ("c", "a", 3), ("c", "d", 100)]
parent = {j: j for j in "abcd"}
def find(x):
while parent[x] != x:
x = parent[x]
return x
total = 0
for a, b, cost in sorted(roads, key=lambda r: r[2]):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
total += cost
print(total)That road to d is a critical road, and the second prediction is no accident.
Every critical road is in the backbone
A critical road is the only link between its two sides, so every spanning tree has to include it, the cheapest one included. Here is the city with its backbone drawn, then its critical roads marked. Watch where they land:
The cheapest backbone has no spare links, so every critical road in the city is one of its links.
Eight junctions and nine roads. Each number is the cost of laying fibre along that road. 8 nodes, 9 edges, undirected. At central.
For Meridian that's a planning lesson, not only a theorem. The cheapest backbone has no redundancy at all, so any road the city can't afford to lose, the fibre can't afford to lose either. Resilience costs extra links beyond the tree.
Part 2: weak points, in one DFS
Critical roads and critical junctions come out of the same low-link DFS. When a child finishes, fold its low-link into its parent's, then check:
low[child] > disc[parent]: the roadparent–childis critical;low[child] >= disc[parent], for a parent that isn't the DFS root: the parent junction is critical;- the DFS root is critical only if it had two or more DFS children.
That third rule is easy to forget, and forgetting it marks every root:
Only c is critical (closing it strands d), but this also reports a, which is the DFS root. Fix the root's rule.
Run the DFS from every undiscovered junction, and a network in several pieces is covered too. Each piece gets its own root and its own low-links.
Trace the union-find half on a small network with an island:
The report, drawn from your own code
Below, your code runs on a city extract with a ferry-only island. It builds the
backbone road by road, then marks the critical roads in red and badges each
junction with its piece. Try it: add ["east", "yard", 11] and every critical
road on the mainland disappears. Join the island instead with
["dock", "pier", 12], and the piece count drops while two new critical roads
appear.
Your network report. The backbone grows cheapest first, then one DFS marks every weak point.
Putting it together
Two helpers and a dict:
The weak-points helper is the iterative low-link DFS from the bridges lesson, with the root-child count added. Here's what the whole report costs:
| Part | Tool | Cost |
|---|---|---|
| pieces | union-find | nearly O(E) |
| backbone | Kruskal's (the same unions, sorted) | O(E log E) |
| critical roads | low-link DFS | O(V + E) |
| critical junctions | the same DFS | free |
| whole report | O(E log E) |
The sort is the most expensive step. Everything structural about the city comes
from one sort, one union-find pass and one DFS. Space is O(V + E): near
holds every road, parent one entry per junction, and disc/low/the DFS stack
together hold at most one entry per junction too.
❓ Cross-question: "Why not reuse the backbone to find the critical roads? They're all in it." Every critical road is in the backbone, but not every backbone link is critical. On a ring, the backbone is all but one road and none of them is critical, because the skipped road is the way round. Being critical depends on the roads the backbone left out, so it needs the full network.
Idioms & real-world patterns
One report, many consumers
This is how production network tools are built. A planning service computes components, spanning structure and single points of failure once, whenever the map changes, and every other system (routing, dispatch, alerting) reads the result rather than recomputing it. Keeping the helpers separate, as above, lets each part be tested against the slow definitions from its own lesson.
What comes next for Meridian
With the network modelled, Meridian can start moving things through it. That means shortest routes that survive negative adjustments, all-pairs distances between depots, and heuristic search fast enough for a live map. Those build on this section: routing on a DAG uses the topological order from the first lesson, and every route stays inside one piece of the network.
⚡ Advanced: keeping it current
Roads open and close all day. Recomputing the whole report is O(E log E), which is fine every few minutes for a city. Keeping the answers exact after every single change is a research-grade problem (dynamic connectivity). Most real systems batch the changes and recompute.
Quick practice
junctions = ["m", "n", "o", "p"]
roads = [["m", "n", 3], ["n", "o", 1], ["o", "m", 4]]
parent = {j: j for j in junctions}
def find(x):
while parent[x] != x:
x = parent[x]
return x
pieces, cost = len(junctions), 0
for a, b, c in sorted(roads, key=lambda r: r[2]):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
pieces, cost = pieces - 1, cost + c
print(pieces, cost)The triangle's cheapest backbone costs 1 + 2 = 3, but this prints a total of 6 because it keeps a-b (5) before it ever sees the cheaper roads. Fix the loop so it visits roads in cost order.
🎯 Your turn
Write network_report(junctions, roads). Roads are two-way [a, b, cost], all
costs different. Return:
"pieces": how many separate pieces the network falls into;"backbone": the total cost of the cheapest roads keeping every piece connected;"critical_roads": every road whose closure splits a piece, as[a, b]with a before b, sorted;"critical_junctions": every junction whose closure splits a piece, sorted.
network_report(["a", "b", "c"], [["a", "b", 2], ["b", "c", 3]]) →
{"pieces": 1, "backbone": 5, "critical_roads": [["a", "b"], ["b", "c"]], "critical_junctions": ["b"]}
Hint: one sorted union-find pass for the first two, one low-link DFS per piece for the last two, and don't forget the root rule.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = Meridian's network model is complete. ✅