Biconnected Components

A biconnected component (or block) is a maximal subgraph with no articulation point — any two of its vertices lie on a common cycle. Equivalently: a maximal set of edges such that any two of them lie on a common simple cycle.

Blocks partition the edges of a graph, not the vertices. A vertex can belong to several blocks — and those vertices are exactly the articulation points.

Finding them — $O(V+E)$

Same low-link DFS as articulation points, plus an edge stack. When the condition low[v] >= tin[u] fires, pop edges off the stack down to $(u,v)$: they form one block.

int timer_ = 0;
vector<int> tin, low;
vector<pair<int,int>> stk;
vector<vector<pair<int,int>>> blocks;
 
void dfs(int u, int p) {
    tin[u] = low[u] = ++timer_;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (tin[v]) {                          // back edge
            if (tin[v] < tin[u]) stk.push_back({u, v});
            low[u] = min(low[u], tin[v]);
        } else {
            stk.push_back({u, v});
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= tin[u]) {            // u closes a block
                vector<pair<int,int>> comp;
                while (true) {
                    auto e = stk.back(); stk.pop_back();
                    comp.push_back(e);
                    if (e == make_pair(u, v)) break;
                }
                blocks.push_back(comp);
            }
        }
    }
}

A bridge appears as a block containing exactly one edge.

The block-cut tree

Build a bipartite tree whose nodes are (a) the blocks and (b) the articulation points, with an edge between a block and each articulation point it contains. The result is a tree (a forest, per component). See Block-Cut Tree.

It turns vertex-connectivity questions into tree questions:

Question	On the block-cut tree
Does removing $x$ separate $a$ from $b$?	is $x$ on the path between $a$‘s and $b$‘s block nodes
How many blocks does a path cross?	path length
Which vertices lie on some simple path $a\to b$?	union of the blocks on the tree path
Which vertices lie on every simple path $a\to b$?	the articulation points on the tree path

Edge vs vertex connectivity — keep them straight

	Edge version	Vertex version
Critical element	bridge	articulation point
Components	2-edge-connected components	biconnected components (blocks)
Condensed structure	bridge tree	block-cut tree
Partitions	vertices	edges
DFS condition	low[v] > tin[u]	low[v] >= tin[u]

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.

Menger’s theorem

The maximum number of internally vertex-disjoint $u$-$v$ paths equals the minimum number of vertices whose removal separates $u$ from $v$. This is why “2-connected” and “two disjoint paths between every pair” are the same statement, and why vertex connectivity is computed with max flow on a vertex-split graph.

Typical problems

• Vertices/edges lying on at least one simple cycle
• “Is there a path from $a$ to $b$ avoiding vertex $x$?”
• Minimum edges to add so the graph becomes biconnected
• Counting simple paths through a required vertex
• Cactus graphs (every edge in at most one cycle) — every block is a single edge or a single cycle, which makes many hard problems tractable

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