Block-Cut Tree

Quick Revisit

• USE WHEN: Answering 2-connectivity queries or reducing a graph with cut vertices to a tree structure
• INVARIANT: The block-cut tree is a forest where each biconnected component and each cut vertex is a node; cut vertices connect the blocks they belong to
• TIME: O(V + E) | SPACE: O(V + E)
• CLASSIC BUG: Forgetting that a cut vertex belongs to multiple biconnected components — it must appear as a separate node connected to each of its blocks
• PRACTICE: 05-ladder-graphs

The block-cut tree compresses a graph into a tree of biconnected components and cut vertices, letting you answer 2-connectivity queries with standard tree techniques.

Difficulty	[Advanced]
CF Rating Range	1800-2100
Prerequisites	Bridges and Articulation Points, DFS and Tree DFS

---

Intuition

You know how to find bridges and articulation points. But what can you do with them? How do you answer queries about 2-connectivity?

Consider: "Are vertices $u$ and $v$ 2-vertex-connected?" or "Which cut vertices lie on every path from $u$ to $v$?" Knowing which vertices are cut vertices is not enough -- you need a structural decomposition of the entire graph.

Biconnected Components

A biconnected component (or block) is a maximal subgraph with no cut vertex. Equivalently, for any two vertices $u,v$ in the same block, there exist at least two vertex-disjoint paths between them. Removing any single vertex from a block keeps it connected.

Key properties:

• Every edge belongs to exactly one block.
• Two blocks share at most one vertex -- and that vertex is a cut vertex.
• A bridge is a block by itself (a degenerate block with one edge).
• A single isolated vertex with no edges is its own trivial block.

The Block-Cut Tree

The block-cut tree is a bipartite tree with two kinds of nodes:

• Block nodes: one per biconnected component.
• Cut-vertex nodes: one per articulation point.

Edges: a block node connects to a cut-vertex node if and only if that cut vertex belongs to that block. Non-cut vertices appear in exactly one block and do not get their own tree nodes (they are "inside" their block node).

This tree captures the entire 2-connectivity structure. Any query about separating vertices, 2-connected subgraphs, or paths through cut vertices reduces to a tree query on the block-cut tree.

When Does This Appear?

Codeforces tags: graphs, dfs and similar, trees. Typical rating: 1800-2200. Common scenarios:

• "Remove vertex $v$ -- how many connected components?" -> degree of $v$ in block-cut tree (if $v$ is a cut vertex).
• "Are $u$ and $v$ 2-vertex-connected?" -> same block check.
• "How many cut vertices separate $u$ from $v$?" -> path query on block-cut tree.
• Graph problems that become tree problems after block-cut decomposition.

Common Traps

• Confusing 2-edge-connectivity (bridges) with 2-vertex-connectivity (cut vertices). They use similar DFS but produce different decompositions.
• Assuming a block always has $\ge 3$ vertices. A bridge edge forms a block of size 2. An isolated vertex is a block of size 1.
• Forgetting that cut vertices belong to multiple blocks.

What the Code Won't Teach You

Why build a block-cut tree at all? Many graph problems that seem hard become easy on trees. The block-cut tree lets you reason about 2-connectivity structurally. Questions like "how many biconnected components does a path from $u$ to $v$ cross?" or "what is the minimum number of vertices to remove to disconnect $u$ from $v$?" become straightforward tree queries once you have the block-cut tree.

The block-cut tree is a tree -- so use tree techniques. This sounds obvious but people often don't follow through. Once you have the block-cut tree, questions about paths in the original graph become LCA or path-query problems on the tree. You can use HLD on the block-cut tree. You can use Euler tour. The reduction is powerful precisely because it converts graph questions to tree questions.

Implementation is subtle enough to get wrong on the first attempt. Unlike many algorithms where the idea translates cleanly to code, the block-cut tree construction has several steps that interact: the stack-based component extraction, the new node numbering, and the tree edge construction. Any one of these can be subtly wrong and produce a tree that looks correct on small tests but fails on graphs with multiple articulation points.

The "rooms and doorways" mental model. Think of each biconnected component as a "room" and each articulation point as a "doorway" between rooms. The block-cut tree is the floor plan: rooms connected by doorways, in a tree shape. Any path in the original graph maps to a path in this floor plan -- through rooms and doorways alternately.

Debugging the block-cut tree requires printing the tree, not just the components. When your answer is wrong, dump the block-cut tree: print every tree node (block or cut vertex) and its neighbors. Compare against a hand-drawn decomposition. The most common bug -- wrong node numbering -- becomes immediately visible when you print the tree.

The block-cut tree size can surprise you. For a graph with $n$ vertices, the block-cut tree can have up to $2n-1$ nodes (when every edge is a bridge). Allocate arrays of size $2n$, not $n$. Under-allocation causes subtle out-of-bounds writes that corrupt other data.

  Block-cut tree size examples:
  +---------------------+--------+-----------+----------+
  | Graph structure     | Verts  | Blocks    | BCT nodes|
  +---------------------+--------+-----------+----------+
  | Single cycle        |   n    |    1      |    1     |
  | Path (all bridges)  |   n    |   n-1     |  2n-2    |
  | Star (all bridges)  |   n    |   n-1     |  2n-2    |
  | Complete graph      |   n    |    1      |    1     |
  +---------------------+--------+-----------+----------+
  Worst case: 2n - 1 nodes.  Always allocate 2n.

The block-cut tree makes "2-connectivity queries" into tree queries. Once you have the block-cut tree, questions like "are vertices $u$ and $v$ 2-vertex-connected?" reduce to "are they in the same block?" which is a simple membership check. Questions like "how many articulation points lie on every path from $u$ to $v$?" become LCA path queries on the tree. The code builds the tree; the insight is knowing which graph questions become which tree questions.

GRAPH QUESTION -> TREE QUESTION TRANSLATION:

  ┌───────────────────────────────────────────────────────┐
  │ Graph question              │ Tree operation           │
  ├───────────────────────────────────────────────────────┤
  │ Are u,v 2-connected?        │ Same block node?         │
  │ # APs on path u->v?         │ # AP-type nodes on path  │
  │ Remove vertex w: is u->v    │ Is w an AP on the        │
  │   still connected?          │   tree path u->v?         │
  │ # biconnected components   │ # block nodes in tree    │
  │   on path u->v?              │   (count on path / 2 +1) │
  └───────────────────────────────────────────────────────┘

---

Visual Intuition

Diagram 1: A Graph and Its Biconnected Components

Consider this graph with 9 vertices and clear block structure:

  Graph G:
  
      1 ------- 2
      |         |
      |         |
      4 ------- 3          6 ------- 7
          \                /         |
           \              /          |
            5 -----------.           8
                                     |
                                     9
  
  Edges: (1,2) (2,3) (3,4) (1,4) (4,5) (5,6) (6,7) (7,8) (8,9) (6,8)

Identify the blocks:

  Block B1: {1, 2, 3, 4}     -- cycle 1-2-3-4, no cut inside
  Block B2: {4, 5}           -- bridge edge (4,5)
  Block B3: {5, 6}           -- bridge edge (5,6)
  Block B4: {6, 7, 8}        -- cycle 6-7-8, no cut inside
  Block B5: {8, 9}           -- bridge edge (8,9)
  
  Cut vertices: 4, 5, 6, 8

Visual with blocks labeled:

  +-------------+     +-----+     +-----+     +----------+     +-----+
  | B1          |     | B2  |     | B3  |     | B4       |     | B5  |
  |  1 --- 2   |     |     |     |     |     |  6 --- 7 |     |     |
  |  |     |   |     |     |     |     |     |   \   /  |     |     |
  |  4 --- 3   *--4--*--5--*--5--*--6--*     |    8    |*--8--* 9   |
  |             |     |     |     |     |     |         |     |     |
  +-------------+     +-----+     +-----+     +---------+     +-----+
  
  * = cut vertex (shared between blocks)

Diagram 2: The Block-Cut Tree

Now build the block-cut tree. Create a node for each block and each cut vertex, then connect them:

  Block-Cut Tree:
  
       [B1]
        |
       (4)          <-- cut vertex
        |
       [B2]
        |
       (5)          <-- cut vertex
        |
       [B3]
        |
       (6)          <-- cut vertex
        |
       [B4]
        |
       (8)          <-- cut vertex
        |
       [B5]

  Legend:  [Bx] = block node    (v) = cut vertex node

This is a path-shaped tree because the original graph had a "chain" of blocks. In general, the block-cut tree can be any tree shape.

Diagram 3: Construction Walkthrough -- Edge Stack on a Bowtie

Two triangles sharing vertex 3. Vertex 3 is a cut vertex and -- crucially -- it belongs to both biconnected components, which is the case the implementation has to get right.

  Graph:
        1
       / \
      2---3---4
              \
              5

  Edges: (1,2),(2,3),(1,3),(3,4),(4,5),(3,5)

  Two cycles glued at vertex 3:
    Cycle A: 1-2-3-1
    Cycle B: 3-4-5-3
  Vertex 3 is the gluing point (= cut vertex).

DFS from vertex 1 maintains an edge stack. When we cross a tree edge, push it. When we close a cycle via a back edge, push that too. When we return from a child $v$ to $u$ and find $\text{low}[v]\ge \text{disc}[u]$, pop the stack down to $(u,v)$ -- those edges form one biconnected component.

  Step  Action                     Edge stack (bottom -> top)        Block popped
  ----  ------                     -----------------------------     ------------
   1    enter 1
   2    enter 2, push (1,2)        [(1,2)]
   3    enter 3, push (2,3)        [(1,2),(2,3)]
   4    back edge 3->1, push (3,1) [(1,2),(2,3),(3,1)]
   5    return 3->2: low[3]=disc[1]=disc[1] of root=0
   6    return 2->1: child=2, low[2]=0 >= disc[1]=0
         pop down to edge (1,2):
         out come (3,1),(2,3),(1,2)
         vertices touched = {1,2,3}                                  B1 = {1,2,3}
   7    enter 3 again? No -- 3 already visited. Continue at 1:
        actually 3 is visited via tree from 2, so DFS continues
        from 3 to its remaining unvisited neighbors when we
        first entered 3 in step 3. Re-trace:

  (Rewinding -- in real DFS, vertex 3's children are explored in
   order before we return. After back edge (3,1), we still have
   neighbors 4 and 5 of vertex 3 to visit.)

   3a   enter 4 from 3, push (3,4) [(1,2),(2,3),(3,1),(3,4)]
   3b   enter 5 from 4, push (4,5) [(1,2),(2,3),(3,1),(3,4),(4,5)]
   3c   back edge 5->3, push (5,3) [(1,2),(2,3),(3,1),(3,4),(4,5),(5,3)]
   3d   return 5->4: low[5]=disc[3]
   3e   return 4->3: child=4, low[4]=disc[3]=disc[3]
         pop down to edge (3,4):
         out come (5,3),(4,5),(3,4)
         vertices touched = {3,4,5}                                  B2 = {3,4,5}
   3f   continue: low[3]=disc[1] (back edge in step 4), so
        return to 2, then to 1; remaining stack [(1,2),(2,3),(3,1)]
        gets popped as block {1,2,3} when we return to root --
        this is the step-7 pop above.

The trace is non-linear because DFS interleaves tree descents with returns; the important bookkeeping is that vertex 3 stays present in both B1's pop and B2's pop. That is how the same cut vertex ends up as a member of two blocks.

Resulting bipartite tree. Block nodes [B1], [B2]; cut-vertex node $⟨3⟩$. Block B1 contains 3, so connect [B1] -- $⟨3⟩$. Block B2 also contains 3, so connect [B2] -- $⟨3⟩$.

  Block-cut tree:

      [B1: 1,2,3] --- (3) --- [B2: 3,4,5]

  Three nodes, two edges, bipartite (block <-> cut-vertex).
  Vertex 3 sits at the only cut-vertex node and connects to both blocks.

This is the canonical mental picture for every block-cut construction: the edge stack chops the DFS tree into blocks at each low[v] >= disc[u] boundary, and cut vertices bridge consecutive pops.

Diagram 4: Graph to Block-Cut Tree Transformation

A second example showing the full transformation at a glance:

  Original graph:                Biconnected components:
                                 
  1---2---3---5---6              B1: {1,2,3,4}  (edges 1-2, 2-3, 3-4, 4-1)
  |       |   |                  B2: {3,5}      (edge 3-5)
  4-------+   7                  B3: {5,6,7}    (edges 5-6, 6-7, 7-5)
                                 
  Articulation points: 3, 5     Block-cut tree:
                                 
                                 [B1]---<3>---[B2]---<5>---[B3]
                                 
  [Bx] = block node (biconnected component)
  <x>  = cut vertex node

Diagram 5: Block-Cut Tree Node Types

Detailed breakdown of what each node type represents in a larger tree:

  Block-cut tree structure:
  
  [B1]---<3>---[B2]---<5>---[B3]---<8>---[B4]
                       |
                      <6>
                       |
                      [B5]
  
  Block nodes [Bx]:              Cut vertex nodes <x>:
  +-----------------------------+------------------------------+
  | Represent biconnected       | Represent articulation       |
  |   components (maximal       |   points from the graph      |
  |   2-connected subgraphs)    |                              |
  | Contain >= 1 edge           | Connected to every block     |
  | Leaf blocks have exactly    |   that contains them         |
  |   1 cut vertex (or none     | Removing <x> disconnects     |
  |   if entire graph is        |   adjacent blocks            |
  |   biconnected)              |                              |
  +-----------------------------+------------------------------+
  
  Degree of <x> in BCT = number of biconnected components containing x
  
  Non-cut vertices do NOT appear as tree nodes.
  They live "inside" exactly one block node.

Diagram 6: Answering Connectivity Queries on Block-Cut Tree

How 2-connectivity questions reduce to tree path queries:

  Query: Are nodes 1 and 6 in the same biconnected component?
  
  [B1:1,2,3,4]---<3>---[B2:3,5]---<5>---[B3:5,6,7]
  
  Node 1 is in B1, Node 6 is in B3
  Path in BCT: B1 -- <3> -- B2 -- <5> -- B3
  Path contains cut vertices 3 and 5
  --> 1 and 6 are NOT 2-vertex-connected
  --> Removing vertex 3 OR vertex 5 disconnects them
  
  Query: Are nodes 5 and 7 in the same biconnected component?
  Both in B3 --> YES, they are 2-vertex-connected
  No single vertex removal can disconnect them
  
  General rule:
  +------------------------------------------------------------+
  | u and v are 2-vertex-connected                             |
  |   iff they map to the SAME block node in the BCT.          |
  |                                                            |
  | The cut vertices on the BCT path from tree_node(u) to      |
  |   tree_node(v) are exactly the vertices whose removal      |
  |   disconnects u from v.                                    |
  +------------------------------------------------------------+

Diagram 7: Removing a Cut Vertex -- Effect on Components

What happens when you remove an articulation point from the graph? The block-cut tree makes this visible:

  Original graph:                 Block-cut tree:

    1 --- 2 --- 5 --- 6          [B1:1,2,3] --- <2> --- [B2:2,4]
    |     |     |                                  \
    3     4     7                                   <4> --- ... (if exists)
                                                    
                                  [B3:5,6,7] --- <5> --- [B2:2,5]

  Remove vertex 2 (cut vertex):
  
    Graph splits into:            In BCT: remove <2>, adjacent blocks
    {1, 3}  and  {4}  and         become disconnected subtrees.
    {5, 6, 7}                     
                                  Number of pieces = degree of <2> in BCT
  Degree of <2> in BCT = 3       (one piece per adjacent block, minus
  -> removing 2 creates 3         overlaps from shared blocks... but
    components? Not quite:        each block minus the removed vertex
                                  gives one component)

  General formula:
  +----------------------------------------------------------+
  | Components after removing cut vertex v =                  |
  |   degree(v) in the block-cut tree                        |
  |   (= number of blocks containing v)                      |
  +----------------------------------------------------------+

Diagram 8: The "Rooms and Doorways" Model

THE "ROOMS AND DOORWAYS" MODEL:

  Original Graph:
  
    1──2──3──4──5
    │  │     │  │
    6──7     8──9
         │
        10──11
         │   │
        12──13

  Block-Cut Tree (rooms = blocks, doors = APs):

  ┌─────────────────────────────────────────┐
  │                                         │
  │  ┌─Room 1─┐    ┌─Room 2─┐   ┌─Room 3─┐│
  │  │1 2 6 7 │─(3)─│ 3 4 8 │─(5)─│5 9    ││
  │  │        │door │       │door│       ││
  │  └────────┘    └───┬───┘   └────────┘│
  │                     │(10)             │
  │                ┌─Room 4─┐             │
  │                │10 11 12│             │
  │                │   13   │             │
  │                └────────┘             │
  └─────────────────────────────────────────┘

  To go from vertex 1 to vertex 9:
  Room1 -> door(3) -> Room2 -> door(5) -> Room3
  Path crosses 2 articulation points (doors).

Diagram 9: DFS Tree -> Original Graph -> Block-Cut Tree Transformation

TRANSFORMATION PIPELINE:

  Step 1: Original Graph     Step 2: DFS + low[]     Step 3: Block-Cut Tree
  
  1──2──4                    1 (disc=1,low=1)        ┌──────┐
  │ ╱│                       │╲                       │Block1│
  │╱  │                      │  2 (disc=2,low=1)     │{1,2,3}│
  3   5                      │   ╲                    └──┬───┘
                             3    4 (disc=4,low=2)       │(2)
                            (d=3,  ╲                  ┌──┴───┐
                            low=1)  5(d=5,low=4)      │Block2│
                                                      │{2,4,5}│
  APs found: vertex 2                                └──────┘
  (low[4]=2 >= disc[2]=2)
  
  Block-cut tree has 2 block nodes + vertex 2 as AP node = 3 tree nodes

Worked Example: Full Block-Cut Tree Construction

Build the block-cut tree step by step for a graph with 8 vertices.

  Graph G (8 vertices, 10 edges):
  
      0 ----- 1          5 ----- 6
      |       |          |       |
      |       |          |       |
      3 ----- 2 ------- 4       7
                          \     /
                           \   /
                            (back to 5)
  
  Adjacency:
    0: [1, 3]    1: [0, 2]    2: [1, 3, 4]    3: [0, 2]
    4: [2, 5]    5: [4, 6, 7]  6: [5, 7]       7: [5, 6]

Step 1: DFS with disc/low arrays (start from vertex 0)

  DFS traversal order: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
  
  Vertex  disc  low   Parent   Notes
  ------  ----  ----  ------   -----
    0       0     0     -1     root
    1       1     0      0     tree edge 0->1
    2       2     0      1     tree edge 1->2
    3       3     0      2     tree edge 2->3, back-edge 3->0: low[3]=min(3,0)=0
    4       4     4      2     tree edge 2->4
    5       5     5      4     tree edge 4->5
    6       6     5      5     tree edge 5->6, back-edge 6->? (see below)
    7       7     5      6     tree edge 6->7, back-edge 7->5: low[7]=min(7,5)=5
  
  Back-edge propagation:
    low[7] = min(low[7], disc[5]) = min(7, 5) = 5
    low[6] = min(low[6], low[7])  = min(6, 5) = 5
    low[5] = min(low[5], low[6])  = min(5, 5) = 5
    low[4] = min(low[4], low[5])  = min(4, 5) = 4  (no improvement)
    low[3] = min(low[3], disc[0]) = min(3, 0) = 0  (back-edge 3->0)
    low[2] = min(low[2], low[3])  = min(2, 0) = 0
    low[1] = min(low[1], low[2])  = min(1, 0) = 0
    low[0] = min(low[0], low[1])  = min(0, 0) = 0

Step 2: Identify articulation points

  For each non-root u with child v: cut vertex if low[v] >= disc[u]
  For root u: cut vertex if >= 2 DFS-tree children
  
  Vertex 0: root, only 1 DFS child (1)        --> NOT cut
  Vertex 1: child 2, low[2]=0 >= disc[1]=1?   0 >= 1? NO  --> NOT cut
  Vertex 2: child 3, low[3]=0 >= disc[2]=2?   0 >= 2? NO
            child 4, low[4]=4 >= disc[2]=2?   4 >= 2? YES --> CUT vertex
  Vertex 3: no DFS children                    --> NOT cut
  Vertex 4: child 5, low[5]=5 >= disc[4]=4?   5 >= 4? YES --> CUT vertex
  Vertex 5: child 6, low[6]=5 >= disc[5]=5?   5 >= 5? YES --> CUT vertex
  Vertex 6: child 7, low[7]=5 >= disc[6]=6?   5 >= 6? NO  --> NOT cut
  Vertex 7: no DFS children                    --> NOT cut
  
  Articulation points: {2, 4, 5}

Step 3: Identify biconnected components using the edge/vertex stack

  When low[v] >= disc[u], pop stack down to v to form a block with u.
  
  At vertex 2, child 3: low[3]=0, disc[2]=2 --> 0 < 2, no block pop
  At vertex 2, child 4: low[4]=4, disc[2]=2 --> 4 >= 2, pop block!
  
  Stack pops produce these blocks:
  
  Block B0: {5, 6, 7}      -- popped when returning to 5 from child 6
                               (low[6]=5 >= disc[5]=5)
  Block B1: {4, 5}          -- popped when returning to 4 from child 5
                               (low[5]=5 >= disc[4]=4)
  Block B2: {2, 4}          -- popped when returning to 2 from child 4
                               (low[4]=4 >= disc[2]=2)
  Block B3: {0, 1, 2, 3}    -- popped when DFS finishes at root
                               (remaining vertices on stack)

Step 4: Construct the block-cut tree

  Nodes: B0, B1, B2, B3 (block nodes) + 2, 4, 5 (cut vertex nodes)
  
  Edges (block <-> cut vertex it contains):
    B3:{0,1,2,3} contains cut vertex 2 --> B3 -- <2>
    B2:{2,4}     contains cut vertex 2 --> B2 -- <2>
    B2:{2,4}     contains cut vertex 4 --> B2 -- <4>
    B1:{4,5}     contains cut vertex 4 --> B1 -- <4>
    B1:{4,5}     contains cut vertex 5 --> B1 -- <5>
    B0:{5,6,7}   contains cut vertex 5 --> B0 -- <5>
  
  Final block-cut tree:
  
  [B3:0,1,2,3]---<2>---[B2:2,4]---<4>---[B1:4,5]---<5>---[B0:5,6,7]
  
  Total tree nodes: 4 blocks + 3 cut vertices = 7
  Total tree edges: 6
  
  Verify: tree on 7 nodes has 6 edges. Correct!

---

C++ STL Reference

Function / Class	Header	What it does	Time
vector<vector<int>>	<vector>	Adjacency list	--
stack<pair<int,int>>	<stack>	Edge stack for Tarjan's block extraction	$O(1)$ push/pop
vector<vector<int>> blocks	<vector>	Store vertex sets of each block	--
vector<bool> is_cut	<vector>	Mark articulation points	--
min(low[u], disc[v])	--	Update low-link via back edge	$O(1)$
min(low[u], low[v])	--	Update low-link via tree edge	$O(1)$

The main data structures are plain vectors and a stack of edges. No fancy STL needed -- this is a DFS-based algorithm.

---

Implementation (Contest-Ready)

Version 1: Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

struct BlockCutTree {
    int n, timer = 0, block_cnt = 0;
    vector<vector<int>> adj, tree;
    vector<int> disc, low, comp;
    vector<bool> is_cut;
    stack<int> stk;

    BlockCutTree(int n) : n(n), adj(n), disc(n, -1), low(n), is_cut(n) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        stk.push(u);
        int children = 0;
        for (int v : adj[u]) {
            if (disc[v] == -1) {
                children++;
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if ((parent == -1 && children > 1) ||
                    (parent != -1 && low[v] >= disc[u])) {
                    is_cut[u] = true;
                }
                if (low[v] >= disc[u]) {
                    // pop a new block
                    int block_id = n + block_cnt++;
                    while (true) {
                        int w = stk.top(); stk.pop();
                        comp[w] = block_id;
                        if (w == v) break;
                    }
                    // u is also in this block but stays on stack
                    // (it may belong to multiple blocks)
                }
            } else if (v != parent) {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

    // Build the block-cut tree. Returns number of tree nodes.
    int build() {
        comp.assign(n, -1);
        for (int i = 0; i < n; i++)
            if (disc[i] == -1)
                dfs(i, -1);

        // Cut vertices get their own node; non-cut vertices
        // keep the block node assigned in comp[].
        // Cut vertex u -> node id = u (reuse original id).
        // Block j -> node id = n + j.
        int tree_sz = n + block_cnt;
        tree.assign(tree_sz, {});

        // For each cut vertex, connect it to all its blocks.
        // We detect blocks of cut vertex by scanning adjacency.
        vector<int> last_block(tree_sz, -1);
        for (int u = 0; u < n; u++) {
            if (is_cut[u]) {
                // u participates in every block that any
                // neighbor's comp points to, plus its own children.
                for (int v : adj[u]) {
                    int b = comp[v];
                    if (b != -1 && last_block[b] != u) {
                        last_block[b] = u;
                        tree[u].push_back(b);
                        tree[b].push_back(u);
                    }
                }
            }
        }
        // Non-cut vertices: their tree representative is comp[v].
        return tree_sz;
    }

    // Which tree node represents vertex v?
    int tree_node(int v) {
        return is_cut[v] ? v : comp[v];
    }
};

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    BlockCutTree bct(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;
        bct.add_edge(u, v);
    }
    bct.build();
    // Now bct.tree is the block-cut tree.
    // Use bct.tree_node(v) to map original vertex -> tree node.
    return 0;
}

Version 2: Explained Version

Same structure, with inline comments explaining the why:

#include <bits/stdc++.h>
using namespace std;

struct BlockCutTree {
    int n, timer = 0, block_cnt = 0;
    vector<vector<int>> adj, tree;
    vector<int> disc, low, comp;
    vector<bool> is_cut;
    stack<int> stk;

    BlockCutTree(int n) : n(n), adj(n), disc(n, -1), low(n), is_cut(n) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        stk.push(u);
        int children = 0;

        for (int v : adj[u]) {
            if (disc[v] == -1) {
                children++;
                dfs(v, u);
                low[u] = min(low[u], low[v]);  // tree edge: inherit child's low

                // Cut vertex detection:
                //   Root with >= 2 children, OR
                //   Non-root where child's subtree can't escape above u
                if ((parent == -1 && children > 1) ||
                    (parent != -1 && low[v] >= disc[u]))
                    is_cut[u] = true;

                // Block extraction: when low[v] >= disc[u], everything
                // on stack from v upward forms a block with u.
                // u stays on stack -- it may belong to more blocks.
                if (low[v] >= disc[u]) {
                    int bid = n + block_cnt++;
                    while (true) {
                        int w = stk.top(); stk.pop();
                        comp[w] = bid;
                        if (w == v) break;
                    }
                }
            } else if (v != parent) {
                low[u] = min(low[u], disc[v]);  // back edge: reach disc[v]
            }
            // For multigraphs: skip by edge index, not parent vertex
        }
    }

    int build() {
        comp.assign(n, -1);
        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) {
                dfs(i, -1);
                // Root may remain on stack (not popped by any child).
                // Assign it to a block -- isolated or single-component root.
                if (comp[i] == -1) comp[i] = n + block_cnt++;
            }
        }

        int tree_sz = n + block_cnt;
        tree.assign(tree_sz, {});

        // Connect each cut vertex to its adjacent blocks.
        // A cut vertex u touches block comp[v] for each neighbor v.
        // last_block[] deduplicates: same block reached via multiple neighbors.
        vector<int> last_block(tree_sz, -1);
        for (int u = 0; u < n; u++) {
            if (!is_cut[u]) continue;
            for (int v : adj[u]) {
                int b = comp[v];
                if (b != -1 && last_block[b] != u) {
                    last_block[b] = u;
                    tree[u].push_back(b);
                    tree[b].push_back(u);
                }
            }
        }
        return tree_sz;
    }

    int tree_node(int v) { return is_cut[v] ? v : comp[v]; }
};

Handling Multi-Edges

The above uses parent vertex to skip back-edges, which breaks with multi-edges. For multigraphs, store edge indices and skip by edge:

// In dfs, replace `v != parent` with edge-index tracking:
void dfs(int u, int parent_edge) {
    disc[u] = low[u] = timer++;
    stk.push(u);
    int children = 0;
    for (auto [v, eid] : adj[u]) {  // adj stores {neighbor, edge_id}
        if (eid == parent_edge) continue;
        if (disc[v] == -1) {
            children++;
            dfs(v, eid);
            low[u] = min(low[u], low[v]);
            // ... same cut vertex and block extraction logic
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

---

Operations Reference

Operation	Time	Space	Notes
Build block-cut tree	$O(V+E)$	$O(V+E)$	Single DFS pass
Find all cut vertices	$O(V+E)$	$O(V)$	Part of build
Find all blocks	$O(V+E)$	$O(V+E)$	Part of build
"Are $u,v$ in same block?"	$O(1)$	--	Check comp[u] == comp[v] (both non-cut)
"Are $u,v$ 2-vertex-connected?"	$O(1)$	--	Same block and neither is a cut vertex separating them
LCA / path query on tree	$O(\log V)$	$O(V\log V)$	After binary lifting on block-cut tree
Count cut vertices on $u$-$v$ path	$O(\log V)$	--	Count cut-vertex nodes on tree path
"Does removing $v$ disconnect $u$ from $w$?"	$O(\log V)$	--	Check if $v$ is on $u$-$w$ path in block-cut tree

---

Problem Patterns and Tricks

Pattern 1: "Are $u$ and $v$ 2-vertex-connected?"

Two vertices are 2-vertex-connected if and only if they lie in the same biconnected component (same block). After building the block-cut tree, this is a direct lookup.

For non-cut vertices: comp[u] == comp[v].

For cut vertices: they share a block if they are adjacent in the block-cut tree (distance $\le 2$ in the tree, with a block node between them).

Example: CF 962F, CF 732F

Pattern 2: "Which cut vertices separate $u$ from $v$?"

Map $u$ and $v$ to their tree nodes. Find the path between them in the block-cut tree. Every cut-vertex node on this path is a vertex whose removal disconnects $u$ from $v$.

This reduces to a tree path query. Use LCA + binary lifting for $O(\log n)$ per query.

// After building block-cut tree, find all cut vertices on u-v path
// using LCA. Count nodes on path that are cut vertices (id < n).
int count_cuts_on_path(int u, int v) {
    int a = bct.tree_node(u), b = bct.tree_node(v);
    // Walk the tree path from a to b, count nodes with id < n
    // (those are cut vertex nodes)
    // Use standard LCA + path traversal
}

Example: CF 487E

Pattern 3: Convert Graph Queries to Tree Queries

Many hard graph problems become easy once you realize the block-cut tree is a tree. Any tree technique -- LCA, HLD, Euler tour, centroid decomposition -- can then be applied.

Typical flow:

1. Build block-cut tree.
2. Map original vertices to tree nodes.
3. Answer queries on the tree (LCA, path max, subtree sums, etc.).
4. Translate answers back to the original graph.

Example: CF 1391E

Pattern 4: 2-Edge-Connected Components (Bridge Tree)

The bridge tree is the edge-connectivity analog. Instead of biconnected components (cut vertices), you contract 2-edge-connected components (bridges). Construction is similar:

• Find bridges via DFS.
• Each 2-edge-connected component becomes a node.
• Bridges become tree edges.

The bridge tree is simpler because components don't overlap (no vertex belongs to multiple 2-edge-connected components). Use it when the problem is about edge removal, not vertex removal.

Example: CSES 2076 (Necessary Roads), CF 1000E

Pattern 5: Counting Paths Through Cut Vertices

Given a graph, count the number of simple paths that pass through a specific cut vertex. The block-cut tree gives the subtree sizes on each side, enabling combinatorial counting.

For a cut vertex $v$ in the block-cut tree with subtrees of sizes $s_1,s_2,\dots ,s_k$ (after removing $v$), the number of paths through $v$ is:

$$\sum _{i<j}{s}_i\cdot s_j$$

Example: CF 1076E

Pattern 6: Merging Block Information

Sometimes each block carries a value (e.g., "minimum weight edge in the block") and you need to aggregate along a path. Assign values to block nodes in the block-cut tree, then do a path query.

This pattern appears when each biconnected component has some aggregate property (size, edge count, minimum/maximum weight) and queries ask about paths.

Example: CF 487E, CF 962F

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                     BLOCK-CUT TREE CHEAT SHEET                   |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - 2-vertex-connectivity queries                                |
|   - "Remove vertex v, how many components?"                      |
|   - Path queries through cut vertices                            |
|   - Converting graph problem to tree problem                     |
+------------------------------------------------------------------+
| BUILD:                                                           |
|   1. Tarjan DFS, push vertices to stack                          |
|   2. When low[v] >= disc[u], pop stack -> one block              |
|   3. Mark cut vertices (root: children>1, else: low[v]>=disc[u]) |
|   4. Create tree: block nodes + cut vertex nodes, connect them   |
+------------------------------------------------------------------+
| KEY LOOKUPS:                                                     |
|   tree_node(v) = is_cut[v] ? v : comp[v]                        |
|   Same block?  -> comp[u] == comp[v]  (non-cut vertices)         |
|   Separates?   -> cut vertex on tree path between u and v        |
+------------------------------------------------------------------+
| COMPLEXITY:  Build O(V+E)  |  Query O(log V) with LCA           |
| SPACE:       O(V+E)        |  Tree has <= 2V-1 nodes             |
+------------------------------------------------------------------+
| WATCH OUT:                                                       |
|   - Multi-edges: track edge index, not parent vertex             |
|   - Disconnected graphs: DFS from every component                |
|   - Cut vertex belongs to MULTIPLE blocks                        |
+------------------------------------------------------------------+

---

Gotchas and Debugging

Mental Traps (from reflection)

"I know how to find articulation points, so I understand block-cut trees."

Finding articulation points is only the prerequisite. Building the block-cut tree is a further step: you need to identify the biconnected components, number them as new block nodes, and wire up the tree structure. Many people stop at "finding articulation points" and never actually build the tree.

"The block-cut tree has $n$ nodes."

No. It has one node per articulation point plus one new node per biconnected component. Non-articulation vertices are "inside" their block node -- they do not get their own tree nodes. If the graph has 10 vertices and 3 biconnected components, the block-cut tree has up to 13 nodes (3 block nodes + up to 10 cut-vertex nodes, though most vertices are not cut vertices). Getting node numbering wrong when building the tree is a common implementation bug.

"Biconnected = 2-edge-connected."

These are different. Biconnected (2-vertex-connected) means no single vertex removal disconnects the component. 2-edge-connected means no single edge removal disconnects it. For block-cut-tree problems, you need 2-vertex-connectivity. For bridge-tree problems, you need 2-edge-connectivity. Verify which one the problem requires.

"I remove articulation points and the remaining pieces are the biconnected components."

Articulation points are still present in the block-cut tree as explicit nodes. The tree doesn't "remove" them -- it shows how the components are glued together through them. Each cut vertex connects to every block that contains it.

"I can answer 2-connectivity queries by just checking if two nodes share a neighbor."

Sharing a neighbor does not imply 2-vertex-connectivity. Two nodes are 2-vertex-connected only if they lie in the same biconnected component -- meaning there exist two vertex-disjoint paths between them. The block-cut tree answers this in $O(1)$: check if both nodes map to the same block node. Guessing from local adjacency is unreliable.

  Shares neighbor but NOT 2-connected:

     u ------- w ------- v         w is a cut vertex
                                   Remove w -> u and v disconnect
     u and v share neighbor w,
     but they are NOT 2-vertex-connected.

  In the block-cut tree:
     [B1:u,w] --- <w> --- [B2:w,v]
     u is in B1, v is in B2 -> different blocks -> NOT 2-connected

"The block-cut tree is only useful for theoretical analysis, not for actual contest solutions."

The block-cut tree is a practical contest tool. Once built ($O(V+E)$), it converts graph connectivity questions into tree path/LCA queries. CF 487E (Tourists, rating 2400) requires HLD on the block-cut tree. CF 1726E (Edge Groups) uses combinatorics on the block-cut tree. If you skip building the tree, you have no efficient way to answer multi-query 2-connectivity problems.

  Without BCT:                     With BCT:
  +--------------------------+     +--------------------------+
  | Q queries about 2-conn.  |     | Build BCT once: O(V+E)  |
  | Each query: O(V+E) DFS   |     | Each query: O(log V)    |
  | Total: O(Q*(V+E))        |     | Total: O(V+E + Q*log V) |
  | 10^5 queries -> TLE       |     | 10^5 queries -> OK       |
  +--------------------------+     +--------------------------+

Trap: "Every edge in the block-cut tree corresponds to an edge in the original graph."

Block-cut tree edges connect block nodes to articulation-point nodes -- these aren't edges from the original graph. They represent containment: "this articulation point belongs to this biconnected component." Trying to map block-cut tree edges back to specific original edges is a category error.

BLOCK-CUT TREE EDGE SEMANTICS:

  Original graph:                Block-cut tree:
  
  1───2───3───4                  [B1]───(3)───[B2]───(5)───[B3]
  |   |   |   |                    │             │             │
  5───6   7───8                   (1)           (7)           (9)
      |       |                   (2)           (4)
      3───────5                   (5)           (8)
                                  (6)
  Block B1: {1,2,3,5,6}
  Block B2: {3,4,5,7,8}         Block-cut tree edge (3)─[B1]
  Block B3: {5,9,...}            means "vertex 3 is IN block B1"
                                 NOT "edge 3─something exists"

Trap: "The block-cut tree has the same diameter as the original graph."

The diameter changes because block-cut tree alternates between block nodes and articulation nodes. A path of length $d$ in the original graph may traverse $k$ blocks, giving a block-cut tree path of length $2k-1$ (alternating block -> AP -> block -> ...). Distances in the block-cut tree count "hops between components," not edge distances.

DISTANCE DISTORTION IN BLOCK-CUT TREE:

  Original graph path: 1─2─3─4─5  (length 4)
  
  But 3 is an articulation point separating two blocks:
  
  Block-cut tree path: [B1]─(3)─[B2]  (length 2)
  
  ┌─────────────────────────────────────────────────┐
  │ Original distance:    4 edges                   │
  │ Block-cut tree dist:  2 hops                    │
  │                                                 │
  │ The tree measures "how many biconnected          │
  │ components does the path cross?" not              │
  │ "how many edges?"                                │
  └─────────────────────────────────────────────────┘

1. Root Special Case

The DFS root is a cut vertex only if it has $\ge 2$ DFS-tree children. The standard low[v] >= disc[u] test does NOT work for the root because disc[root] = 0 makes the condition trivially true for every child.

// WRONG: treats root as cut vertex even with 1 child
if (low[v] >= disc[u]) is_cut[u] = true;

// RIGHT: separate root check
if (parent == -1 && children > 1) is_cut[u] = true;
if (parent != -1 && low[v] >= disc[u]) is_cut[u] = true;

2. Multi-Edges (Parallel Edges)

If vertices $u$ and $v$ have two edges between them, skipping by parent vertex will skip both edges, making you miss the back-edge. Use edge indices:

// Store adj as vector<pair<int,int>>: {neighbor, edge_id}
// In DFS, skip by edge_id, not by neighbor identity

3. Disconnected Graphs

The DFS loop must iterate over all vertices. A single dfs(0, -1) misses other connected components. Each component gets its own set of blocks.

for (int i = 0; i < n; i++)
    if (disc[i] == -1)
        dfs(i, -1);

4. Off-by-One in low-link Updates

Back-edge update uses disc[v], not low[v]:

// CORRECT: back edge to already-visited v
low[u] = min(low[u], disc[v]);

// ALSO CORRECT (for biconnected components):
low[u] = min(low[u], low[v]);  // only via tree edge!

Using low[v] for back edges can give wrong results in some cut vertex detection scenarios. Stick with disc[v] for back edges.

5. Block-Cut Tree Size

The block-cut tree has at most $2n-1$ nodes (at most $n-1$ blocks and $n$ potential cut vertices, though in practice fewer). Allocate tree arrays with size $2n$ to be safe.

6. Mapping Cut Vertices to Tree Nodes

A cut vertex $v$ has its own node in the block-cut tree (index $v$) AND appears in multiple blocks. When answering queries, use tree_node(v) which returns $v$ itself for cut vertices, not comp[v] (which holds the last block assigned during DFS -- not meaningful for cut vertices).

7. Stack Residue

After DFS completes, the DFS root may still be on the vertex stack. Handle this: assign it to its block, or create a new block if it is isolated. The implementation above handles this in build().

8. 1-Indexed vs 0-Indexed

Many CF problems use 1-indexed vertices. If you use 0-indexed internally, be careful with the block-cut tree node numbering: cut vertex $i$ has tree node $i$, block $j$ has tree node $n+j$. Off-by-one here is a classic WA source.

---

Common Mistakes

1. Treating every vertex as a block-cut tree node. The block-cut tree has too many nodes and some appear twice when you create a node for every vertex. Non-cut vertices belong to exactly one block and should be absorbed into that block's node -- adding them as separate tree nodes creates a forest instead of a tree. Only create tree nodes for blocks and cut vertices; map each non-cut vertex to its unique block.

Debug Drills

Drill 1 -- Biconnected component: popping too many edges

if (low[to] >= disc[v]) {
    // v is articulation point or root
    vector<pair<int,int>> component;
    while (stk.top() != make_pair(v, to)) {
        component.push_back(stk.top());
        stk.pop();
    }
    // Missing: pop the (v, to) edge itself
}

What's wrong?

You need to also pop (v, to) from the stack and include it in the component:

component.push_back(stk.top());
stk.pop();  // pop (v, to)

Without this, (v, to) stays on the stack and gets included in the next component, corrupting both.

Drill 2 -- Cut vertex appears in block-cut tree but not connected to its blocks

for (int i = 0; i < blocks.size(); i++) {
    int block_node = n + i;  // block nodes start after vertex nodes
    for (int v : blocks[i]) {
        if (is_cut[v])
            tree_adj[v].push_back(block_node);
            // Missing: tree_adj[block_node].push_back(v);
    }
}

What's wrong?

The tree edges must be bidirectional. Missing the reverse edge means LCA / DFS on the tree won't traverse correctly:

tree_adj[v].push_back(block_node);
tree_adj[block_node].push_back(v);

Drill 3 -- Single edge treated as biconnected component of size 1

// A bridge edge (u, v) forms its own "block" with just 2 vertices
// But code treats it as a single-vertex block
if (is_bridge(u, v))
    blocks.push_back({u});  // BUG: missing v

What's wrong?

A bridge forms a block containing both endpoints. Even though the bridge is a "degenerate" biconnected component, it still has 2 vertices and 1 edge:

blocks.push_back({u, v});

Self-Test

Before moving to practice problems, verify you can answer these without looking at the notes:

• [ ] State the definition of a biconnected component -- a maximal set of edges such that every two edges lie on a common simple cycle (equivalently: no articulation point within the component).
• [ ] Describe the block-cut tree's node and edge structure -- two types of nodes (block nodes and cut-vertex nodes), what edges connect them, and how many nodes the block-cut tree has for a given graph.
• [ ] Write Tarjan's articulation point algorithm from memory, including the special case for the DFS root (root is cut iff it has $\ge 2$ DFS-tree children).
• [ ] Explain why low[v] >= disc[u] (not >) is the correct condition for non-root articulation points, and what goes wrong with >.
• [ ] Give one example of a problem that reduces to a block-cut tree query, and explain why the tree structure makes the problem tractable.
• [ ] State how non-articulation vertices relate to biconnected components -- each appears in exactly one component and connects to exactly one block node in the block-cut tree.
• [ ] Explain the difference between 2-vertex-connectivity (biconnected components / block-cut tree) and 2-edge-connectivity (bridge tree), and when to use each.
• [ ] Draw the block-cut tree for a graph with 8 vertices and 2 articulation points -- label each node as either a block node or an articulation-point node, and state the total node count of the tree.
• [ ] Explain why the root of the DFS tree needs special-case handling for articulation-point detection -- write the condition for the root vs. non-root cases.
• [ ] Given a block-cut tree, determine whether removing vertex $v$ disconnects vertices $u$ and $w$ by checking if $v$ is an articulation point on the tree path from $u$ to $w$.
• [ ] Trace the stack-based biconnected component extraction during DFS on a 6-vertex graph with one bridge and one cycle -- show what gets pushed and popped.
• [ ] State the node count formula for the block-cut tree: if the original graph has $n$ vertices and $b$ biconnected components, the block-cut tree has $n+b$ nodes (but only articulation points and block nodes form the tree; non-AP vertices appear inside blocks only).

---

Practice Problems

CF Rating	What You Should Be Able to Do
1200	Find connected components; understand what biconnected means informally.
1500	Find articulation points and bridges using Tarjan's DFS.
1800	Build the block-cut tree explicitly; answer queries like "are $u$ and $v$ 2-connected?" via tree LCA.
2100	Combine block-cut tree with DP or advanced tree queries (e.g., virtual tree on block-cut tree, path min/max).

#	Problem	Source	Difficulty	Key Idea
1	Necessary Roads	CSES 2076	1700	Find all bridges (warm-up for bridge tree)
2	Necessary Cities	CSES 2077	1800	Find all articulation points (direct prereq)
3	Edge Groups	CF 1726E	2100	Block-cut tree + combinatorics on tree
4	Tourists	CF 487E	2400	Block-cut tree + HLD, min in blocks
5	Police Stations	CF 796E	2200	BFS on block-cut tree
6	Centroids	CF 1391E	2100	Block-cut tree structure
7	Edges in Spanning Tree	CF 1000E	2100	Bridge tree (2-edge-connected analog)
8	Biconnected Components	Library Checker	--	Direct implementation test

Work through CSES 2076 and 2077 first -- they drill the prerequisite algorithms. Then CF 1726E and the Library Checker problem for the full block-cut tree. CF 487E is the classic hard application.

---

Further Reading

• cp-algorithms: Biconnected Components -- covers bridges, articulation points, and biconnected components.
• cp-algorithms: Block-Cut Tree -- direct reference for the tree construction.
• CF Blog: Block-Cut Tree Tutorial -- community tutorial with problem links.
• e-maxx (Russian) -- original source for many cp-algorithms articles.
• See: 02-bridges-and-articulation-points.md -- prerequisite algorithm for identifying cut vertices and bridges.