Block-Cut Tree

The block-cut tree (BCT) condenses a connected undirected graph into a tree that captures all of its vertex-connectivity structure.

Construction

Nodes of the BCT:

• one node per block (biconnected component),
• one node per articulation point.

Edges: connect each articulation point to every block containing it.

The result is a tree. Non-articulation vertices belong to exactly one block and are represented by it.

// after computing blocks (as edge lists) and isArt[]
int cntBCT = 0;
vector<int> bctId(n, -1);                 // articulation point -> BCT node
vector<vector<int>> bct;
 
for (int v = 0; v < n; v++)
    if (isArt[v]) { bctId[v] = cntBCT++; bct.push_back({}); }
 
for (auto& blk : blocks) {
    int b = cntBCT++; bct.push_back({});
    set<int> verts;
    for (auto [u, v] : blk) { verts.insert(u); verts.insert(v); }
    for (int v : verts) {
        if (isArt[v]) { bct[b].push_back(bctId[v]); bct[bctId[v]].push_back(b); }
        else bctId[v] = b;                 // non-cut vertex lives in this block
    }
}

Properties

• The BCT of a connected graph is a tree; of a disconnected graph, a forest.
• Leaves of the BCT are always blocks (a leaf block contains exactly one articulation point).
• The number of BCT nodes is $O(V)$; total block sizes are $O(V+E)$.
• A graph is biconnected iff its BCT is a single block node.

What it answers

Question	Answer on the BCT
Does removing $x$ disconnect $a$ from $b$?	$x$ is an articulation point on the tree path from $a$‘s node to $b$‘s node
Vertices on some simple $a\to b$ path	union of vertices of the blocks on that tree path
Vertices on every simple $a\to b$ path	the articulation-point nodes on that tree path
Number of blocks a path visits	tree path length
Minimum edges to make the graph biconnected	$\lceil L/2\rceil$ where $L$ = number of leaf blocks (for a connected graph, $L\ge 2$)
Is there a cycle through both $u$ and $v$?	they lie in the same block

Because it is a tree, all of these become LCA and path queries — $O(\log V)$ each with binary lifting.

The edge analogue: the bridge tree

The bridge tree does the same job for edge connectivity: contract each 2-edge-connected component to a node, keep only the bridges as edges. It is simpler to build (a DSU over non-bridge edges suffices) and answers “how many bridges must a path cross”.

	Block-cut tree	Bridge tree
Handles	vertex removal	edge removal
Node types	blocks and cut vertices	2-edge-connected components only
Build from	biconnected components	bridges + DSU
Bipartite structure	yes (block ↔ cut vertex)	no

Worked use: “count pairs separated by removing $v$”

For a non-articulation $v$ the answer is 0. For an articulation point, root the BCT anywhere, and removing $v$ splits the graph into the components corresponding to $v$‘s BCT subtrees. Precompute the vertex count in each subtree, and the answer is $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ minus the sum of $\left(\genfrac{}{}{0ex}{}{s_i}{2}\right)$ over the resulting pieces.

See also: Biconnected Components · Bridge Tree · Bridges and Articulation Points