Online Bridge Detection, in depth: maintaining bridges under edge insertions with a 2-edge-connected forest, two union-finds and small-to-large re-rooting

The bridge forest and the three insertion cases

Two vertices are 2-edge-connected when they remain connected after removing any single edge. This relation is an equivalence, so it partitions the vertices into 2-edge-connected components (2ECCs). Contract every 2ECC to a single node and the bridges are precisely the edges left between nodes; because any cycle among them would have made them non-bridges, the contracted graph is a forest. This is the bridge tree described in bridges in graphs.

Insertions interact with that forest in only three ways, and the whole algorithm is these three cases:

The count never needs recomputing. A new edge between components is a bridge by definition, since removing it restores the previous disconnection. A new edge inside a tree creates exactly one cycle through the forest path, and every edge on a cycle is not a bridge; edges off that path are unaffected because their removal still separates the same vertex sets. Edges are never un-merged under insertions, which is why union-find, with no deletion support, is enough.

State, re-rooting and the LCA walk

The implementation keeps four arrays over vertices, but only entries for current 2ECC representatives are meaningful:

• ecc: a union-find mapping each vertex to its 2ECC representative. Merging a cycle unions every node on the path into the lowest common ancestor.
• par: the parent of each forest node, stored as a vertex id that may have since been merged away, so every read goes through find_ecc.
• cc: a second union-find over forest nodes whose representative is the root of the tree, used to tell case 2 from case 3 in near-constant time.
• size: vertices per tree, valid at the root, used to decide which tree to re-root when linking.

Linking two trees needs care. The forest is stored with parent pointers, so a node can have only one parent; to hang tree A under a node of tree B, the endpoint in A must first become A's root. Re-rooting reverses the parent pointers along the path from that endpoint to the old root, which costs the path length. Always re-root the smaller tree. A vertex's tree at least doubles each time it is on the re-rooted side, so any vertex is re-rooted at most log₂ n times, and total re-rooting work over all insertions is O(n log n).

Collapsing a cycle needs the lowest common ancestor of two forest nodes. Binary lifting would have to be rebuilt after every re-root, so instead both endpoints walk upward alternately, stamping the nodes they visit with an iteration counter; the first node a walk finds already stamped is the LCA. Alternating matters: it bounds the walk by about twice the length of the path that is about to be destroyed, and each node on that path is merged away permanently. Since there are at most n - 1 merges in the lifetime of the structure, total walking work is O(n) plus union-find costs.

A complete implementation

The full structure in Python. It handles self-loops and parallel edges, which matter in practice: a second physical link between the same two routers is exactly the redundancy you are trying to detect.

class OnlineBridges:
    """Bridges of an undirected multigraph under edge insertions only."""

    def __init__(self, n):
        self.par = [-1] * n          # forest parent as a vertex id (may be stale)
        self.ecc = list(range(n))    # DSU: 2-edge-connected components
        self.cc = list(range(n))     # DSU: trees, representative = tree root
        self.size = [1] * n          # vertices per tree, valid at the root
        self.seen = [0] * n          # LCA stamps
        self.stamp = 0
        self.bridges = 0

    def find_ecc(self, v):
        if v == -1:
            return -1
        root = v
        while self.ecc[root] != root:
            root = self.ecc[root]
        while self.ecc[v] != root:          # path compression
            self.ecc[v], v = root, self.ecc[v]
        return root

    def find_cc(self, v):
        v = self.find_ecc(v)
        root = v
        while self.cc[root] != root:
            root = self.cc[root]
        while self.cc[v] != root:
            self.cc[v], v = root, self.cc[v]
        return root

    def make_root(self, v):
        """Re-root v's tree at v by reversing parent pointers on the path."""
        v = self.find_ecc(v)
        root, child = v, -1
        while v != -1:
            nxt = self.find_ecc(self.par[v])
            self.par[v] = child
            self.cc[v] = root
            child, v = v, nxt
        self.size[root] = self.size[child]

    def merge_path(self, a, b):
        """a and b share a tree: collapse the tree path between them."""
        self.stamp += 1
        path_a, path_b, lca = [], [], -1
        while lca == -1:
            if a != -1:
                a = self.find_ecc(a)
                path_a.append(a)
                if self.seen[a] == self.stamp:
                    lca = a
                    break
                self.seen[a] = self.stamp
                a = self.par[a]
            if b != -1:
                b = self.find_ecc(b)
                path_b.append(b)
                if self.seen[b] == self.stamp:
                    lca = b
                    break
                self.seen[b] = self.stamp
                b = self.par[b]
        for path in (path_a, path_b):
            for v in path:
                if v == lca:
                    break
                self.ecc[v] = lca            # v's tree edge to its parent dies
                self.bridges -= 1

    def add_edge(self, a, b):
        a, b = self.find_ecc(a), self.find_ecc(b)
        if a == b:
            return                          # self-loop or inside one 2ECC
        ca, cb = self.find_cc(a), self.find_cc(b)
        if ca != cb:                        # joins two trees: one new bridge
            self.bridges += 1
            if self.size[ca] > self.size[cb]:
                a, b, ca, cb = b, a, cb, ca
            self.make_root(a)               # re-root the smaller tree
            self.par[a] = self.cc[a] = b
            self.size[cb] += self.size[a]
        else:
            self.merge_path(a, b)

Two lines carry most of the subtlety. In merge_path, each node on a walk except the LCA is unioned into the LCA and decrements the count once, because the edge from that node to its parent is the bridge being destroyed. In make_root, the cc pointer of every node on the reversed path is set to the new root; nodes off the path still reach it through the old root, whose own pointer now leads there. The union-find here uses path compression only, which gives O(log n) amortised per find; the total is O(n log n + m log n) for n vertices and m insertions, fast enough for millions of edges in a compiled language.

Worked trace and a brute-force oracle

Six vertices, eight insertions, with the bridge count printed after each one. These numbers come from running the code above.

The last row shows why multigraphs must be supported: if the input were deduplicated to a simple graph, the second (2, 3) link would be dropped and the system would report a single point of failure that does not exist. To check it, compare against an oracle on small random graphs; the version below deletes each edge in turn and counts components, which is slow but obviously correct.

import random

def brute_bridges(n, edges):
    def components(skip):
        p = list(range(n))
        def f(x):
            while p[x] != x:
                p[x] = p[p[x]]
                x = p[x]
            return x
        for i, (u, v) in enumerate(edges):
            if i != skip:
                p[f(u)] = f(v)
        return len({f(x) for x in range(n)})
    base = components(-1)
    return sum(components(i) > base for i in range(len(edges)))

rng = random.Random(1)
for _ in range(300):
    n = rng.randint(1, 9)
    g, edges = OnlineBridges(n), []
    for _ in range(rng.randint(0, 14)):
        u, v = rng.randrange(n), rng.randrange(n)
        edges.append((u, v))
        g.add_edge(u, v)
        assert g.bridges == brute_bridges(n, edges), (n, edges)

Assert after every insertion, not only at the end: a bug in re-rooting typically corrupts state silently and shows up several operations later.

Operating it

Answering queries. The count is free. To ask whether an edge (u, v) is a bridge, check that u and v are in different 2ECCs and that one is the forest parent of the other: find_ecc(par[find_ecc(u)]) == find_ecc(v) or the symmetric test. To list all bridges, iterate over current 2ECC representatives with a parent. Whether two vertices survive any single link failure is find_ecc(u) == find_ecc(v).

Mapping back to physical edges. The forest stores component relationships, not the original edge ids. If operators need the name of the link that is a bridge, keep a map from each forest edge to the input edge that created it, set in case 2. Case 3 never needs it, because destroyed bridges are simply forgotten.

Memory and scale. Five integer arrays of length n. For ten million vertices in a compiled language that is around 200 MB with 32-bit ints; in Python, lists of ints cost several times that, so switch to array or NumPy-backed storage, or port the loop to C++ or Rust. Recursion is never used, so deep paths do not overflow the stack.

Persistence and recovery. The state is a pure function of the insertion sequence. Log insertions durably and rebuild on restart, or snapshot the arrays periodically. A snapshot taken mid-operation is invalid, so snapshot between calls.

Failure modes

Reading a stale parent. Using par[v] without find_ecc after a merge walks into a vertex that is no longer a component representative. Symptoms are LCA walks that never terminate or counts that go negative.

Re-rooting the larger tree. The code stays correct but the O(n log n) bound disappears; a long chain grown from one end turns quadratic.

Non-alternating LCA walk. Walking all the way up from one endpoint first costs the full depth, not the cycle length, and the amortised argument breaks.

Deduplicating edges. Collapsing parallel edges before insertion reports bridges that are not bridges, as the worked example showed.

Expecting deletions to work. Union-find cannot split, so removing an edge requires a different structure. If the sequence is known ahead of time, the segment-tree-over-time idea from offline dynamic connectivity extends to bridges, but only with a structure whose updates can be undone; this class, with its path compression and many-node merges, is not a drop-in. Fully dynamic online 2-edge connectivity is possible with polylogarithmic amortised structures from the dynamic-graph literature, notably the work of Holm, de Lichtenberg and Thorup, but they are intricate and rarely worth implementing outside research.

Trade-offs

In most production settings the honest choice is between the first two. If the graph only grows, or grows in long phases between rare deletions, use the incremental forest and rebuild from scratch when a deletion arrives.

What to do next

1. Decide whether your graph is insert-only, insert-mostly, or fully dynamic; pick from the trade-off table accordingly.
2. Copy the class and the brute-force oracle, run the randomised test, then add tests with self-loops and parallel edges from your real data.
3. Add the forest-edge to input-edge map if operators need link names, and expose count, is-bridge and survives-one-failure queries.
4. Benchmark on a growth sequence shaped like yours, including the worst case of a chain grown from one end, to confirm re-rooting stays small-to-large.
5. Log insertions durably and test that a rebuild from the log reproduces the same count.
6. For deletions, prototype with periodic full rebuilds before reaching for dynamic structures.