x. Bridges and Biconnectivity

One lowlink DFS on an undirected (multi)graph gives bridges, articulation points, 2-edge-connected components and biconnected components (blocks). Contracting them gives trees (the bridge tree, the block-cut tree) on which “must every path use this edge/vertex?” becomes a tree path question. Extensions: 3-edge-connected components, strong orientations (Robbins), bridges under edge insertions, ear decompositions and $st$-numberings.

Lowlink DFS

${\text{low}}_v$ = smallest $\text{tin}$ reachable from $v$‘s DFS subtree using tree edges downward and at most one back edge. For a tree edge $u\to v$:

• $(u,v)$ is a bridge iff ${\text{low}}_v>{\text{tin}}_u$;
• $u$ is an articulation point iff ${\text{low}}_v\ge {\text{tin}}_u$ for some child $v$ (non-root $u$), or the root has $\ge 2$ children;
• when ${\text{low}}_v\ge {\text{tin}}_u$, the vertices popped from the stack down to $v$, plus $u$, form a block.

Skip the parent edge id, not the parent vertex, so parallel edges are handled.

struct Lowlink {                                           // undirected multigraph, edges given as pairs
    vector<vector<pair<int, int>>> g; vector<int> tin, low, isBridge, isArt; vector<vector<int>> blocks;
    Lowlink(int n, const vector<pair<int, int>>& E) : g(n), tin(n, -1), low(n), isBridge(sz(E)), isArt(n) {
        for (int i = 0; i < sz(E); i++) { auto [a, b] = E[i]; g[a].push_back({b, i}); if (a != b) g[b].push_back({a, i}); }
        int timer = 0; vector<int> st;
        auto dfs = [&](auto&& self, int u, int pe) -> void {
            tin[u] = low[u] = timer++; st.push_back(u); int kids = 0;
            for (auto [v, e] : g[u]) {
                if (e == pe) continue;
                if (tin[v] >= 0) { low[u] = min(low[u], tin[v]); continue; }
                kids++; self(self, v, e); low[u] = min(low[u], low[v]);
                if (low[v] > tin[u]) isBridge[e] = 1;
                if (low[v] >= tin[u]) {
                    if (pe >= 0 || kids > 1) isArt[u] = 1;
                    blocks.push_back({u});
                    while (true) { int x = st.back(); st.pop_back(); blocks.back().push_back(x); if (x == v) break; }
                }
            }
        };
        for (int s = 0; s < n; s++) if (tin[s] < 0) { dfs(dfs, s, -1); if (sz(st) == 1 && g[s].empty()) blocks.push_back({s}); st.clear(); }
    }
};

(Recursion depth = DFS depth; for $10^6$-vertex paths use an explicit stack or a bigger stack.) Self-loops never belong to a block; a bridge appears as a 2-vertex block.

Proof: the lowlink criteria

In an undirected DFS every non-tree edge joins an ancestor and a descendant. Bridge: removing tree edge $(u,v)$ separates $v$‘s subtree from the rest iff no edge other than $(u,v)$ joins the subtree to the outside; the outside endpoints of such edges would be proper ancestors of $v$, i.e. have $\text{tin}\le {\text{tin}}_u$, so the condition is exactly ${\text{low}}_v>{\text{tin}}_u$ (with parallel copies of $(u,v)$ counting as back edges, hence skipping by edge id). Articulation point: removing non-root $u$ separates child $v$‘s subtree from $u$‘s parent iff no back edge from the subtree reaches a proper ancestor of $u$: ${\text{low}}_v\ge {\text{tin}}_u$. The root’s child subtrees are only connected through the root, so it is a cut vertex iff it has at least two children. Blocks: when ${\text{low}}_v\ge {\text{tin}}_u$, the vertices of $v$‘s subtree still on the stack (those not already split off into deeper blocks) together with $u$ are 2-connected among themselves and separated from the rest by $u$, so they form a maximal block.

Bridge tree and block-cut tree

• 2-edge-connected components: DSU over all non-bridge edges (or DFS that never crosses bridges). Contracting them leaves a forest whose edges are the bridges: the bridge tree.
• Block-cut tree: a bipartite tree with one node per vertex and one node per block, joining each block to its vertices (the “articulation points only” variant drops non-cut vertices).

Question	Answer
bridges on every $u$–$v$ path	bridge-tree path between their components
vertices on every simple $u$–$v$ path	cut vertices on the block-cut tree path
vertices on some simple $u$–$v$ path	union of the blocks on the block-cut tree path
is there a simple cycle through $u$ and $v$?	same block
pairs disconnected by deleting cut vertex $x$	subtree sizes around $x$ in the block-cut tree
min edges to add to make it 2-edge-connected	$\lceil L/2\rceil$, $L$ = leaves of the bridge tree ($L\ge 2$)
min edges to make it biconnected	$\max (\lceil L/2\rceil ,d-1)$: $L$ leaf blocks, $d$ = most components left by deleting one cut vertex (Eswaran–Tarjan)
count of pairs separated by removing cut vertex $v$	root the block-cut tree anywhere; removing $v$ splits the graph into $v$‘s BCT-subtree pieces of size $s_i$, answer $=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)-{\sum }_i\left(\genfrac{}{}{0ex}{}{s_i}{2}\right)$

	Edge version	Vertex version
critical element	bridge	articulation point
components	2-edge-connected components	biconnected components (blocks)
condensed structure	bridge tree	block-cut tree
condensation partitions	vertices	edges
DFS condition	${\text{low}}_v>{\text{tin}}_u$	${\text{low}}_v\ge {\text{tin}}_u$
disjoint-paths theorem	Menger (edge): max edge-disjoint $u$–$v$ paths = min edge cut	Menger (vertex): max internally-disjoint $u$–$v$ paths = min vertex cut, both via max flow on a vertex-split graph

The most common mistake is building a bridge tree when the problem needs a block-cut tree, or contracting vertices when the blocks should be edges.

Proof sketch: $\lceil L/2\rceil$ edges for 2-edge-connectivity

Every leaf component of the bridge tree is attached by a single bridge, so in the augmented graph it needs a new edge incident to it; one new edge touches at most two leaves, giving $\ge \lceil L/2\rceil$. For the construction, list the leaves in DFS order ${\ell }_1,\dots ,{\ell }_L$ and add edges ${\ell }_i\leftrightarrow {\ell }_{i+\lfloor L/2\rfloor }$ (plus one extra if $L$ is odd). Every tree edge $e$ separates the leaves into two sets that are contiguous in the cyclic DFS order, each nonempty and one of size $\le L/2$; such a cyclic interval always contains some ${\ell }_i$ whose partner lies outside it, so some new edge crosses $e$, putting $e$ on a cycle. Hence no bridges remain.

Strong orientation (Robbins)

A connected undirected graph can be oriented to become strongly connected iff it is bridgeless. Construction: orient tree edges downwards and back edges upwards in a DFS. With bridges present, the same DFS orientation makes every 2-edge-connected component strongly connected, and each bridge is necessarily one-way between its two sides. Nash-Williams: every $2k$-edge-connected graph has a $k$-arc-connected orientation.

vector<pair<int, int>> strongOrientation(int n, const vector<pair<int, int>>& E) {   // empty if a bridge exists or disconnected
    vector<vector<pair<int, int>>> g(n); for (int i = 0; i < sz(E); i++) g[E[i].first].push_back({E[i].second, i}), g[E[i].second].push_back({E[i].first, i});
    vector<int> tin(n, -1), low(n); vector<pair<int, int>> res(sz(E)); int timer = 0; bool bad = false;
    auto dfs = [&](auto&& self, int u, int pe) -> void {
        tin[u] = low[u] = timer++;
        for (auto [v, e] : g[u]) {
            if (e == pe) continue;
            if (tin[v] < 0) { res[e] = {u, v}; self(self, v, e); low[u] = min(low[u], low[v]); if (low[v] > tin[u]) bad = true; }
            else { low[u] = min(low[u], tin[v]); if (tin[v] < tin[u]) res[e] = {u, v}; }
        }
    };
    dfs(dfs, 0, -1);
    if (bad || count(all(tin), -1)) return {};
    return res;
}

Proof: Robbins' theorem

A bridge oriented either way leaves one side unable to reach the other, so bridgeless is necessary. Conversely, with tree edges down and back edges up, the root reaches everything along tree edges. Every vertex $v\ne$ root reaches a proper ancestor: since $({\text{par}}_v,v)$ is not a bridge, ${\text{low}}_v<{\text{tin}}_v$, so some vertex in $v$‘s subtree (reachable from $v$ downwards) has a back edge to a proper ancestor of $v$. Repeating, $v$ reaches the root. So every vertex reaches the root and the root reaches every vertex.

Mixed graphs (some edges already directed, others free): still polynomial, via the Boesch–Tindell reduction — model each undirected edge’s unknown orientation as contributing $\pm 1$ to a degree-balance constraint and solve a circulation with demands; strong orientability of the free edges is exactly feasibility of that circulation.

Bridges online

Edges arrive one by one; maintain the number of bridges and 2-edge-connected components in $O(n\log n+m\alpha (n))$ total: keep the forest of 2-edge-connected components with parent pointers and a DSU of connected components. An edge inside a component compresses the tree path between its ends into one component (every edge on it stops being a bridge); an edge between components re-roots the smaller tree and hangs it below the other.

struct OnlineBridges {
    vector<int> par, d2, dcc, csz, seen; int bridges = 0, it = 0;
    OnlineBridges(int n) : par(n, -1), d2(n), dcc(n), csz(n, 1), seen(n) { iota(all(d2), 0); iota(all(dcc), 0); }
    int f2(int v) { if (v < 0) return -1; int r = v; while (d2[r] != r) r = d2[r]; while (d2[v] != r) { int x = d2[v]; d2[v] = r; v = x; } return r; }
    int fcc(int v) { v = f2(v); int r = v; while (dcc[r] != r) r = dcc[r]; while (dcc[v] != r) { int x = dcc[v]; dcc[v] = r; v = x; } return r; }
    void makeRoot(int v) {
        int root = v, child = -1;
        while (v != -1) { int p = f2(par[v]); par[v] = child; dcc[v] = root; child = v; v = p; }
        csz[root] = csz[child];
    }
    void mergePath(int a, int b) {
        ++it; vector<int> pa, pb; int lca = -1;
        while (lca < 0) {
            if (a != -1) { a = f2(a); pa.push_back(a); if (seen[a] == it) { lca = a; break; } seen[a] = it; a = par[a]; }
            if (b != -1) { b = f2(b); pb.push_back(b); if (seen[b] == it) { lca = b; break; } seen[b] = it; b = par[b]; }
        }
        for (auto* p : {&pa, &pb}) for (int v : *p) { d2[v] = lca; if (v == lca) break; --bridges; }
    }
    void addEdge(int a, int b) {
        a = f2(a), b = f2(b); if (a == b) return;
        int ca = fcc(a), cb = fcc(b);
        if (ca != cb) { ++bridges; if (csz[ca] > csz[cb]) swap(a, b), swap(ca, cb); makeRoot(a); par[a] = dcc[a] = b; csz[cb] += csz[a]; }
        else mergePath(a, b);
    }
};

Proof sketch: invariants and $O(n\log n)$

Invariant: the 2-edge-connected components form a forest whose edges (parent pointers) are exactly the current bridges. A new edge between two trees is a new bridge; re-rooting the smaller tree at the endpoint and attaching it keeps a forest. A new edge inside a tree closes a cycle with the tree path between its endpoints; every bridge on that path now lies on a cycle and no other bridge is affected, so the path’s components merge into one (at the LCA, found by walking both ends up alternately with timestamps; walking costs at most twice the number of merged components, each merge removing one forever). Re-rooting costs the size of the smaller tree; a vertex is in the smaller tree $O(\log n)$ times (its tree size doubles each time), giving $O(n\log n)$.

3-edge-connected components

$u\sim v$ iff no two edges separate them (local edge connectivity $\ge 3$). Tsin’s one-pass DFS: ${\text{deg}}_v$ counts back edges crossing $v$‘s parent edge, and chains of vertices that must end in the same class are absorbed through a DSU; $O((n+m)\alpha )$ (Library Checker “Three-Edge-Connected Components”).

vector<vector<int>> threeEdgeCC(int n, const vector<pair<int, int>>& E) {
    vector<vector<int>> g(n); for (auto [a, b] : E) if (a != b) g[a].push_back(b), g[b].push_back(a);
    vector<int> dsu(n); iota(all(dsu), 0);
    auto find = [&](int x) { while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]]; return x; };
    int timer = 0; vector<int> in(n), out(n), deg(n), low(n, INT_MAX), path(n, -1);
    auto absorb = [&](int a, int b) { int ra = find(a), rb = find(b); if (ra != rb) dsu[rb] = ra; deg[a] += deg[b]; };
    auto dfs = [&](auto&& self, int v, int p) -> void {
        in[v] = ++timer;
        for (int w : g[v]) {
            if (w == p) { p = -1; continue; }                // skip one copy of the parent edge
            if (in[w]) {
                if (in[w] < in[v]) { deg[v]++; low[v] = min(low[v], in[w]); }
                else { deg[v]--; int& u = path[v]; for (; u != -1 && in[u] <= in[w] && in[w] <= out[u]; u = path[u]) absorb(v, u); }
                continue;
            }
            self(self, w, v);
            if (path[w] == -1 && deg[w] <= 1) { deg[v] += deg[w]; low[v] = min(low[v], low[w]); continue; }
            if (!deg[w]) w = path[w];
            if (low[w] < low[v]) { low[v] = low[w]; swap(w, path[v]); }
            for (; w != -1; w = path[w]) absorb(v, w);
        }
        out[v] = timer;
    };
    for (int i = 0; i < n; i++) if (!in[i]) dfs(dfs, i, -1);
    vector<vector<int>> by(n), res; for (int i = 0; i < n; i++) by[find(i)].push_back(i);
    for (auto& c : by) if (sz(c)) res.push_back(c);
    return res;
}

The proof of Tsin’s algorithm is long (it simulates contracting “2-edge cuts” along DFS paths); the code is verified against brute force over all pairs of removed edges. For 3-vertex-connectivity, SPQR trees (Hopcroft–Tarjan, linear but intricate) are the tool; contests use them rarely.

4-edge-connected components and general $k$-edge-connectivity (static or dynamic, i.e. “does the graph stay $k$-edge-connected under edge insertions/deletions”) extend the same idea but need genuinely more intricate machinery (sparsification, or the dynamic-connectivity structures of Dynamic Connectivity run per connectivity level); cited here rather than derived, since $k\ge 4$ edge-connectivity is near the rarest end of what any contest asks for, and a from-scratch implementation under contest time is almost never the right call even when it is asked for.

Ear decompositions and $st$-numbering

An ear decomposition writes a graph as a cycle plus paths (ears) whose endpoints lie on earlier ears. Whitney: a graph is 2-edge-connected iff it has an ear decomposition, and 2-vertex-connected iff it has an open one (ear endpoints distinct). An $st$-numbering orders the vertices $s=v_1,\dots ,v_n=t$ so that every other vertex has a neighbour before and after it; it exists iff the graph plus the edge $st$ is biconnected, and it yields an acyclic orientation with a single source $s$ and single sink $t$ (used in planarity testing and in “orient to make every vertex lie on an $s$–$t$ path”).

vector<int> stNumbering(int n, vector<pair<int, int>> E, int s, int t) {   // empty if impossible
    E.insert(E.begin(), {s, t}); vector<vector<int>> g(n);
    for (auto [a, b] : E) g[a].push_back(b), g[b].push_back(a);
    vector<int> vis(n, -1), par(n, -1), ord, it(n); vector<vector<int>> back(n);
    { vector<int> st{s}; vis[s] = 0; ord.push_back(s);
      while (sz(st)) { int x = st.back(); if (it[x] == sz(g[x])) { st.pop_back(); continue; }
        int y = g[x][it[x]++];
        if (vis[y] < 0) vis[y] = sz(ord), ord.push_back(y), par[y] = x, st.push_back(y);
        else if (vis[y] < vis[x]) back[y].push_back(x); } }
    if (sz(ord) != n) return {};
    vector<char> done(n); vector<vector<int>> ears;
    for (int x : ord) {
        done[x] = 1;
        for (int y : back[x]) {
            vector<int> ear{x, y};
            while (!done[ear.back()]) done[ear.back()] = 1, ear.push_back(par[ear.back()]);
            if (ear.back() == x && ear != vector<int>{s, t, s}) return {};
            ears.push_back(ear);
        }
    }
    vector<int> w(n, 1);
    for (int i = sz(ears) - 1; i >= 1; i--) for (int j = 1; j + 1 < sz(ears[i]); j++) w[ears[i][0]] += w[ears[i][j]];
    if (w[s] + w[t] != n) return {};
    vector<pair<int, int>> iv(n, {-1, -1}); iv[s] = {0, w[s] - 1}; iv[t] = {w[s], n - 1};
    for (int i = 1; i < sz(ears); i++) {
        const auto& e = ears[i]; int r = e[0];
        for (int j = sz(e) - 2; j >= 1; j--) {
            int x = e[j];
            if (iv[e.front()].first < iv[e.back()].first) iv[x] = {iv[r].second - w[x] + 1, iv[r].second}, iv[r].second -= w[x];
            else iv[x] = {iv[r].first, iv[r].first + w[x] - 1}, iv[r].first += w[x];
        }
    }
    vector<int> res(n, -1);
    for (int i = 0; i < n; i++) { if (iv[i].first != iv[i].second || iv[i].first < 0) return {}; res[iv[i].first] = i; }
    return res;
}

Proof: ears characterise 2-edge-connectivity

If a graph has an ear decomposition, every edge lies on the initial cycle or on an ear, and an ear together with a path between its endpoints in the earlier part forms a cycle, so no edge is a bridge. Conversely, in a bridgeless connected graph take any cycle; while some edge is not covered, pick an uncovered edge $(u,v)$ with $u$ covered (connectivity), and since $(u,v)$ is not a bridge there is a path from $v$ back to the covered part avoiding $(u,v)$; the edge plus the part of that path until it first hits the covered set is an ear. For vertex 2-connectivity the same argument with “no cut vertex” makes the ear’s endpoints distinct. The DFS-based construction above takes ears as (back edge + tree path up to the first already-assigned vertex), in DFS order.

Parallel algorithms: Tarjan–Vishkin computes blocks in $O(\log n)$ PRAM time from any spanning tree plus Euler-tour prefix computations; sequentially just use the lowlink DFS.