STEP 15 · GRAPHS · CAN THE SUBTREE ESCAPE OVER ME? · HARD

Bridges in a Graph (Critical Connections)

WHAT IT SAYS

Find every edge whose removal disconnects the graph.

WHAT IT'S REALLY ASKING

"Run a DFS and look at any tree edge u→v. Everything below v got discovered THROUGH that edge — so the edge is redundant only if the subtree under v has some OTHER way back up: a back edge climbing to u or above. No such escape route means every path from v's subtree to the rest of the world funnels through this one edge. Bridge-ness is a question each subtree can answer about itself with a single number: the highest ancestor it can reach."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Remove each edge and re-check connectivity

O(E · (V + E)) — a complete traversal per edge

For every edge: delete it, run a full DFS/BFS to test whether the graph still holds together (or whether the edge's endpoints still reach each other), restore it. Collect the edges whose removal splits the graph.

WHERE THE WORK IS WASTED — Each trial re-derives global connectivity from nothing, but the trials share almost everything: deleting edge A and deleting edge B leave graphs that differ in two edges out of E, and their connectivity verdicts hinge on largely identical cycle structure. The deeper miss is that bridge-ness is a LOCAL property with a global costume — an edge is a bridge exactly when it lies on no cycle, and cycle membership is decidable for ALL edges simultaneously by one traversal that watches where back edges land. Paying a full traversal per edge to test cycle membership one edge at a time is testing n facts that one witness pass certifies together.

KEY OBSERVATION — THE UNLOCKlink

A bridge is a tree edge nothing vaults over.

Set the stage with a structural fact about DFS on an undirected graph: every edge is either a TREE edge (it discovered a new vertex) or a BACK edge (it points from a vertex to one of its own ancestors) — cross edges cannot exist, because when DFS at u sees an already-visited v that is not u's ancestor, v's exploration would have had to finish without ever probing the u–v edge, impossible in an undirected graph. So the entire graph is a DFS tree plus ancestor-pointing shortcuts. Now classify. A back edge is never a bridge: it closes a cycle with the tree path it vaults over. A tree edge u→v is a bridge PRECISELY WHEN no back edge connects the subtree rooted at v to u or anything above u — because any escape route from that subtree to the rest of the graph must be some back edge (that is all there is), and a back edge landing at u or higher creates an alternative path around the edge; landing strictly below u helps nothing, the funnel remains. One direction gives the cycle, the other gives the cut. So each subtree must report one number upward: the earliest-discovered vertex it can reach using its own tree edges plus at most the back edges leaving it. Call it low[v], with disc[v] the DFS discovery timestamp. It composes in post-order like every subtree summary in this course: low[v] = min of disc[v], the low of every tree child, and disc[w] for every back edge v→w. The verdict falls out at the moment child v reports to parent u: if low[v] > disc[u], nothing in v's subtree climbs to u or above — the edge u–v is a bridge. Strictly greater, not ≥: low[v] == disc[u] means the subtree reaches back exactly to u, closing a cycle through u, so the edge survives. One trap is the undirected echo (the same one from cycle detection): the tree edge v→u read backwards looks like a back edge to an ancestor and would poison low[v] with disc[u], hiding every bridge. Exempt the edge you arrived by — track the parent EDGE (by index, so parallel edges are handled: two u–v edges mean neither is a bridge, and node-based exemption would miss that). One DFS, every edge examined once from each side, all bridges reported: O(V + E).

One DFS carrying disc and low, verdict at child-return

O(V + E) time — one pass — O(V) for the two arrays plus stack

Timestamp counter; disc[] = -1 (unvisited), low[]. DFS(u, parentEdge): stamp disc[u] = low[u] = timer++; for each incident edge e to w — skip e == parentEdge; if w unvisited: recurse DFS(w, e), low[u] = min(low[u], low[w]), and if low[w] > disc[u] record edge u–w as a bridge; else (back edge): low[u] = min(low[u], disc[w]). Launch from every unvisited vertex (disconnected graphs). Iterative stack version for deep graphs.

WHAT YOU TRADED — The low-link pass is one traversal but its correctness is a lattice of small exactnesses — strict inequality, parent-EDGE exemption, per-component launches — each of which fails silently if fudged; the delete-and-test method is brutally slow but nearly impossible to get wrong, a legitimate cross-check on small inputs. The transferable lesson: 'does removal disconnect?' converts to 'does anything vault over it?', and vaulting is summarisable per subtree as one min — the widen-the-postorder-contract move again, with low[] as the evidence that travels. The same disc/low machinery, with the verdict test changed, yields articulation points and strongly connected components (Tarjan's SCC).

WATCH THE IDEA RUN

bridge test low[child] > tin[parent]

bridges found —

The definition is 'remove the edge and the graph falls apart' — which suggests removing each edge and re-running a traversal. E traversals. But one DFS already knows everything needed.

step 1 / 13

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Subtree Escape Summary

YOU'LL SEE IT AGAIN WHEN

Criticality of an edge/vertex — 'does removing it disconnect?' — which is really 'does an alternative route (a cycle) cover it?'
Undirected DFS admits only tree and back edges, so all alternative routes are back edges, summarisable per subtree as one earliest-reachable timestamp.
The verdict is decidable at child-return time from two numbers (low[child] vs disc[parent]) — one post-order pass replaces per-edge trials.

SAME BLUEPRINT, DIFFERENT PROBLEM

Articulation Points (same disc/low, verdict low[v] >= disc[u] plus a root special case)Kosaraju's Algorithm (the directed-graph counterpart of structural decomposition)Critical Connections in a Network (this problem's LeetCode name)Redundant Connection (the inverse: find a cycle edge, not a cut edge)

The bar isn't "solved it once." It's "could rebuild it from the observation."