Bridges / articulation (low-link)

46 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four servers are wired: 0–1, 1–2, 2–0, and 1–3. Which single cable, if cut, would split the network? By hand you cut each one and check. Cut 0–1: 0 still reaches 1 through 2. Cut 1–3: server 3 is alone. So 1–3 is critical, a bridge; the others are not because they sit on a cycle.

Cutting each cable and re-checking connectivity costs E checks of E work each. For a network with 100,000 cables that is 10 billion steps. We want one walk through the network that recognises bridges as it goes.

Build the structure, one piece at a time

Piece one: depth-first search from server 0, following cables to unvisited servers. Give each server a discovery time disc[], the moment the walk first reached it. Walk: 0 (time 0), then 1 (time 1), then 2 (time 2), then back to 1 and on to 3 (time 3).

Piece two: the question that decides a bridge. Cable 1–3 is a bridge if, once you are at 3, there is no way back to 1 or above except through that cable. So we need, for each server, the earliest discovery time it can reach using tree cables downward and at most one cable that leads back up. Call it low[].

Piece three: compute low[] on the way back from the recursion. Start low[v] = disc[v]. When a cable from v reaches an already visited server u that is not v's parent, that is a back cable: low[v] = min(low[v], disc[u]). When returning from a child c: low[v] = min(low[v], low[c]).

Piece four, the test, applied when returning from child c to parent v: the cable v–c is a bridge exactly when

low[c] > disc[v]

Returning from 2 to 1: low[2] = 0, which is not greater than disc[1] = 1, so 1–2 is safe. Returning from 3 to 1: low[3] = 3 > 1, so 1–3 is a bridge.

Why it is correct

The invariant: low[v] is the smallest discovery time reachable from v's subtree using any number of tree cables downward plus at most one back cable. If low[c] > disc[v], nothing in c's subtree can climb to v or above without the cable v–c, so cutting it separates the subtree: a bridge. If low[c] ≤ disc[v], some back cable from the subtree lands at v or an ancestor, giving a second route, so the cable is on a cycle and not a bridge. Skipping the cable to the direct parent matters: otherwise every tree cable would look like a cycle of length two.

Why it is fast

One depth-first search: each server is discovered once, each cable examined twice.

work = V + 2E, against E² for cut-and-recheck

How to recognise it in an interview

Cues: "critical connection", "removing which edge disconnects", "single point of failure", "articulation point". The first thing to say: "a DFS with discovery times and low-links finds every bridge in one pass." Critical Connections in a Network is exactly the routine above. The same low-link idea, applied to directed graphs, is Tarjan's method for strongly connected components.

02The idea in one line

DFS timestamps; an edge is a bridge if the child cannot reach back above it.

Reach for it when: Critical connections, articulation points, strongly connected components.

Cost: O(V + E) time.

03The walk-through, step by step

The video works one example: Critical Connections on a 4-node graph with one bridge. These are its captions in order, so you can follow without the video or check a step you missed.

1. DFS stamps each node with a discovery time; low = earliest time reachable
2. Visit 0: disc = low = 0
3. Visit 1: disc = low = 1
4. Visit 2: disc = low = 2
5. 2 sees visited 0: back edge, low[2] = 0
6. Back at 1: low[2] = 0 ≤ disc[1], 2 can climb above, not a bridge
7. Visit 3: disc = low = 3
8. Back at 1: low[3] = 3 > disc[1] = 1, edge 1–3 is a bridge
9. Back at 0: low[1] = 0 ≤ disc[0], 1 can climb above, not a bridge
10. 0 sees visited 2: back edge, low[0] = 0
11. Only 1–3 is critical: removing it disconnects node 3
12. One DFS with timestamps: O(V + E)

04Asked at Google

3 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Clone / traverse with a visited map, Implicit graph (states as nodes).