Bridge Tree

Contract every 2-edge-connected component of an undirected graph to a single node, keeping only the bridges as edges. The result is a tree (or forest), because every remaining edge is a bridge and bridges cannot lie on cycles.

Construction — $O(V+E)$

1. Find all bridges with the low-link DFS.
2. Union the endpoints of every non-bridge edge in a DSU. Each resulting set is a 2-edge-connected component.
3. For each bridge $(u,v)$, add a tree edge between find(u) and find(v).

// step 1: bridges (see the bridges page), marked in isBridge[edgeId]
DSU dsu(n);
for (auto [id, u, v] : edges)
    if (!isBridge[id]) dsu.unite(u, v);
 
vector<vector<int>> tree(n);
for (auto [id, u, v] : edges)
    if (isBridge[id]) {
        int a = dsu.find(u), b = dsu.find(v);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

An alternative one-pass construction assigns component ids directly during the bridge DFS (do not descend across a bridge), which avoids the DSU entirely.

Properties

• The bridge tree has one node per 2-edge-connected component and one edge per bridge.
• $\#\text{nodes}-1=\#\text{bridges}$ for a connected graph.
• A graph is 2-edge-connected iff its bridge tree is a single node.
• Every edge of the bridge tree is a bridge of the original graph.

What it answers

Question	On the bridge tree
Number of bridges on any $u\to v$ path	tree distance between their components
Are $u,v$ still connected if edge $e$ fails?	$e$ is a bridge on their tree path
Vertices disconnected from $u$ by removing bridge $e$	subtree size on the far side of $e$
Minimum edges to add for 2-edge-connectivity	$\lceil L/2\rceil$ where $L$ = number of leaves of the bridge tree
Maximum bridges any path crosses	the tree’s diameter

The "$\lceil L/2\rceil$" result is worth remembering: pair up leaves across the tree (leaf $i$ with leaf $i+L/2$ in DFS order), and each added edge kills two leaves. It is the standard answer to “make the road network resilient to any single road closure”.

The vertex analogue

Block-cut trees do the same for vertex connectivity. Bridge trees are simpler and more common; reach for the block-cut tree only when the problem removes vertices rather than edges.

Worked example: “count pairs of vertices whose connection survives every single edge failure”

Build the bridge tree, note the component sizes $s_i$, and the answer is ${\sum }_i\left(\genfrac{}{}{0ex}{}{s_i}{2}\right)$ — pairs inside a 2-edge-connected component have two edge-disjoint paths (Menger), so no single edge failure separates them. Pairs in different components are separated by the bridges between them.

Related: strong orientation

Robbins’ theorem. A connected undirected graph has an orientation making it strongly connected iff it is bridgeless. Concretely: orient every DFS tree edge downward and every back edge upward. If a bridge exists, no orientation works — because a bridge oriented one way makes the far side unreachable. See Strong Orientation.

See also: Bridges and Articulation Points · Block-Cut Tree · DSU