bridges in a graph

Some links in a network are the only thing holding two regions together — cut that one link and the regions drift apart. A bridge (or cut edge) of an undirected graph is exactly such an edge: one whose removal increases the number of connected components, splitting a connected piece in two. Like a single physical bridge between two halves of a city, it is the sole connection across a gap, and losing it severs everything that depended on crossing there.

The defining property is clean: an edge is a bridge if and only if it lies on no cycle. The intuition is that if an edge (u, v) belonged to a cycle, there would be a second, edge-disjoint route from u to v going the long way around the cycle, so deleting (u, v) would not disconnect anything — the alternate route survives. With no such cycle, the edge is the unique path and its loss disconnects. This translates straight into a one-pass DFS test using low-link values. Compute disc(u) (discovery time) and low(u) (earliest discovery time reachable from u's subtree via tree edges plus at most one back edge) as usual. A tree edge (u, v), with v the child, is a bridge exactly when low(v) > disc(u): this says nothing in v's subtree can reach back up to u or any earlier vertex through a back edge, so the tree edge to v is the only connection — no cycle contains it. (Strictly greater than disc(u), unlike the >= used for articulation points; that one difference is the whole distinction.)

Finding bridges runs in O(n + m), one traversal, and it identifies the critical links whose failure would partition a network — essential in reliability analysis of roads, cables, and pipelines, and in decomposing a graph into 2-edge-connected components. Two honest points. First, watch out for parallel edges (two edges between the same pair): if there are two, neither is a bridge, since each provides the other's backup — naive low-link code that ignores multiplicity gets this wrong, so you must avoid treating the immediate parent edge as a back edge while still respecting a genuine second parallel edge. Second, bridges (remove an edge) are distinct from articulation points (remove a vertex); they often coincide but not always, and the strict-versus-nonstrict inequality in the test is exactly what separates them.