2-Edge-Connected Components + Bridge Tree, in depth: one iterative build, must-cross queries with LCA, and the best edge to add

Definitions, and why the result is a tree

Call two vertices u and v 2-edge-connected if they are joined by two paths that share no edge. By Menger's theorem, that is the same as saying no single edge removal separates them. This relation is an equivalence: if u and v survive any single cut, and v and w do too, then so do u and w, because one removed edge can't separate u from w while leaving both connected to v. So the vertices split cleanly into classes, and every vertex lies in exactly one 2ECC.

Vertex biconnectivity behaves differently. A cut vertex belongs to several blocks at once, which is why its tree, the block-cut tree in Biconnected Components, in depth, needs two kinds of node. The bridge tree needs only one.

Why is the result a tree? Two facts. An edge is a bridge if and only if it lies on no cycle. And a cycle in the contracted graph would come from a cycle in the original that uses bridges. So the contraction has no cycles. Every edge between two different 2ECCs is a bridge, and every bridge joins two different 2ECCs. With c components in a connected graph, there are exactly c - 1 bridges.

Building the components and the tree

Building the tree takes three linear passes. First, find bridges with the low-link DFS. Second, label components with a BFS that refuses to cross bridges. Third, emit one tree edge per bridge. The DFS below is iterative, so deep graphs (a path of a million vertices) do not hit the recursion limit. It identifies the edge it arrived by by id, not by the parent vertex. That one detail is what makes parallel edges come out right.

from collections import deque

def bridge_tree(n, edges):
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i)); adj[v].append((u, i))
    tin, low = [-1] * n, [0] * n
    is_bridge, timer = [False] * len(edges), 0
    for root in range(n):
        if tin[root] != -1: continue
        tin[root] = low[root] = timer; timer += 1
        stack = [(root, -1, 0)]                  # vertex, entering edge id, next index
        while stack:
            v, pe, i = stack[-1]
            if i < len(adj[v]):
                stack[-1] = (v, pe, i + 1)
                to, eid = adj[v][i]
                if eid == pe: continue           # skip the edge we came in on, not the vertex
                if tin[to] == -1:
                    tin[to] = low[to] = timer; timer += 1
                    stack.append((to, eid, 0))
                else:
                    low[v] = min(low[v], tin[to])
            else:
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    low[p] = min(low[p], low[v])
                    if low[v] > tin[p]:
                        is_bridge[pe] = True
    comp, c = [-1] * n, 0
    for s in range(n):                           # BFS that never crosses a bridge
        if comp[s] != -1: continue
        comp[s] = c; q = deque([s])
        while q:
            v = q.popleft()
            for to, eid in adj[v]:
                if not is_bridge[eid] and comp[to] == -1:
                    comp[to] = c; q.append(to)
        c += 1
    tree = [[] for _ in range(c)]
    for i, (u, v) in enumerate(edges):
        if is_bridge[i]:
            tree[comp[u]].append((comp[v], i)); tree[comp[v]].append((comp[u], i))
    return is_bridge, comp, tree

Time and memory are O(n + m). Tree edges keep the original edge id, so any answer on the tree maps straight back to a physical link. A self-loop lies on a cycle of length one, so it can never be a bridge, and the code above treats it that way.

Worked example with a parallel edge

The example graph has vertices 0 to 9 and edges 0-1, 1-2, 2-0 (a triangle), 2-3, 3-4, 4-5, 5-3 (a second triangle), 4-6, two parallel edges 6-7, 3-8 and 8-9. The DFS reports four bridges: 2-3, 4-6, 3-8 and 8-9. Edge 6-7 is not a bridge, because its parallel twin keeps 6 and 7 connected if either copy fails. An implementation that skips the parent vertex instead of the parent edge would never look at the second copy, and would wrongly report 6-7 as a bridge.

Labelling gives five components: C0 = {0, 1, 2}, C1 = {3, 4, 5}, C2 = {6, 7}, C3 = {8} and C4 = {9}. The tree has 5 nodes and 4 edges, as it must.

Must-cross queries with LCA

Here is the central fact. The bridges that every u-v path must cross are exactly the tree edges on the path between comp[u] and comp[v]. Any such bridge separates the two sides, so every route uses it. And any bridge off that tree path can be avoided. So the number of single points of failure between u and v is a tree distance, and an LCA structure answers it in O(log n) per query after O(c log c) preprocessing. (LCA via Binary Lifting, in depth explains the jump table.)

class BridgeQueries:
    def __init__(self, tree):
        k = len(tree); self.LOG = max(1, k.bit_length())
        self.depth, self.root_of = [-1] * k, [-1] * k
        self.up = [[0] * k for _ in range(self.LOG)]
        for r in range(k):                       # a forest if the graph is disconnected
            if self.depth[r] != -1: continue
            self.depth[r], self.up[0][r], self.root_of[r] = 0, r, r
            q = deque([r])
            while q:
                x = q.popleft()
                for y, _ in tree[x]:
                    if self.depth[y] == -1:
                        self.depth[y] = self.depth[x] + 1
                        self.up[0][y], self.root_of[y] = x, r
                        q.append(y)
        for j in range(1, self.LOG):
            self.up[j] = [self.up[j - 1][self.up[j - 1][x]] for x in range(k)]

    def lca(self, a, b):
        if self.depth[a] < self.depth[b]: a, b = b, a
        d, j = self.depth[a] - self.depth[b], 0
        while d:
            if d & 1: a = self.up[j][a]
            d >>= 1; j += 1
        if a == b: return a
        for j in range(self.LOG - 1, -1, -1):
            if self.up[j][a] != self.up[j][b]:
                a, b = self.up[j][a], self.up[j][b]
        return self.up[0][a]

    def must_cross(self, a, b):                  # a, b are component ids
        if self.root_of[a] != self.root_of[b]: return None   # not connected at all
        return self.depth[a] + self.depth[b] - 2 * self.depth[self.lca(a, b)]

In the example, rooting at C0: vertex 0 to vertex 9 must cross 3 bridges (2-3, 3-8, 8-9), vertex 0 to vertex 7 must cross 2 (2-3, 4-6), and vertex 1 to vertex 2 crosses 0, because they share a component. A zero answer is the survivability test: u and v stay connected after any single edge failure if and only if comp[u] equals comp[v]. To list the bridges rather than count them, walk both endpoints up to the LCA and read off the stored edge ids. That costs time proportional to the answer.

The best edge to add, and how many to add

Adding an edge between components a and b creates a cycle through the tree path from a to b. Every bridge on that path stops being a bridge. So the single new edge that removes the most bridges joins the two ends of a longest path in the tree: its diameter. Find it with two BFS passes, the first from any node and the second from the farthest node found. In the example, the diameter runs from C4 to C0, with length 3. Adding a link from vertex 9 to any vertex in {0, 1, 2} removes three of the four bridges, and only 4-6 remains.

To remove every bridge, you need at least ceil(L/2) new edges, where L is the number of leaves of the tree. That many always suffices for a tree with at least two nodes. The example has 3 leaves (C0, C2, C4), so 2 edges are enough. The pairing procedure and its proof are in Bridges (Cut Edges) in Graphs, in depth. Weighted variants, where each candidate link has a cost, are NP-hard in general, so treat the diameter and leaf-pairing results as unit-cost answers only.

Testing against an oracle

The oracle is easy to write: for each edge, delete it and check whether its endpoints are still connected. An edge is a bridge exactly when they are not. For a query pair (u, v), count the bridges whose individual removal disconnects u from v, and compare that with must_cross. The code on this page passed that comparison on 400 random multigraphs of up to 9 vertices and 14 edges, including parallel edges, self-loops, isolated vertices and disconnected graphs. Small random multigraphs are the right test, because they produce parallel edges and single-vertex components far more often than hand-written cases do.

Operational guidance

• Size. Everything is linear, so graphs with tens of millions of edges fit on one machine. Use flat arrays (CSR adjacency, integer edge ids) rather than per-vertex lists, and the build is dominated by the two traversals' memory access.
• Rebuild or maintain? If edges are only ever added, the incremental structure in Online Bridge Detection, in depth keeps the 2ECCs current in near-linear total time. Deletions are much harder, so most systems rebuild on a schedule or after topology change events.
• Report in physical terms. Surface the edge ids from the tree, mapped to circuit or link names, together with the component sizes on each side. Operators act on "link X isolates 340 hosts", not on "component 17".
• Track the trend. The number of bridges and the size of the largest 2ECC make good health metrics for a network or dependency graph. A sudden rise in bridges usually means a redundant link was decommissioned.

Failure modes

• Skipping the parent vertex instead of the parent edge. Parallel links get reported as bridges. Real networks have parallel links on purpose, so this bug overstates the risk exactly where redundancy was built.
• Assuming the graph is connected. The tree is then a forest. LCA code with a single root returns garbage for pairs in different trees. The root_of check above returns None for those pairs instead.
• Recursion depth. A recursive DFS on a long chain, such as a fibre ring cut open or a supply chain, overflows the stack long before memory runs out.
• Applying it to directed graphs. Bridges and 2ECCs are undirected notions. For one-way links, you need strong bridges and dominators, which is a different algorithm.
• Confusing edge and vertex failure. A 2ECC can still contain a cut vertex. Two triangles sharing one vertex form one 2ECC, yet that shared router is a single point of failure. If nodes fail, use the block-cut tree.

What to do next

1. Implement bridge_tree and reproduce the example: four bridges, five components, and 6-7 correctly left as a non-bridge.
2. Write the remove-one-edge oracle and run it on a few hundred random small multigraphs, including self-loops and disconnected cases.
3. Add BridgeQueries and answer must-cross queries for pairs of sites you care about. List the actual edge ids for the worst pairs.
4. Compute the tree's diameter and leaf count, then propose the one link, or the ceil(L/2) links, that would remove the most single points of failure.
5. If nodes as well as links can fail, build the block-cut tree too and compare the two reports.