⚙️AlgorithmAdvanced

Block-Cut Tree

Key Points

  • •
    A Block-Cut Tree decomposes an undirected graph into biconnected components (blocks) and articulation points, forming a bipartite tree.
  • •
    Blocks are maximal subgraphs that remain connected after removing any single vertex; articulation points are vertices whose removal increases connected components.
  • •
    You can build the Block-Cut Tree in O(n + m) time with Tarjan’s DFS using discovery times and low-link values.
  • •
    In the Block-Cut Tree, edges connect articulation nodes to the blocks that contain them; non-articulation vertices are absorbed into exactly one block node.
  • •
    Vertex-connectivity queries (e.g., how many articulation points separate two vertices) reduce to path queries on the Block-Cut Tree using LCA.
  • •
    Two original vertices are in the same biconnected component if and only if they share a common block; in the Block-Cut Tree this appears as a shared adjacent block node.
  • •
    The number of articulation points on the unique path between two original vertices equals the count of articulation nodes on the path between their representatives in the Block-Cut Tree.
  • •
    The degree of an articulation node in the Block-Cut Tree equals the number of components formed in its original connected component if that articulation vertex is removed.

Prerequisites

  • →Depth-First Search (DFS) — Tarjan’s algorithm and component extraction rely on DFS tree structure and traversal order.
  • →Graph connectivity (undirected) — Understanding connected components and how removals affect them is essential for articulation and blocks.
  • →Lowest Common Ancestor (LCA) — Many BC-tree queries reduce to path queries solved with LCA and prefix sums.
  • →Tarjan’s low-link technique — Computing articulation points and biconnected components uses discovery times and low-link values.
  • →Trees and forests — The Block-Cut Tree is a forest; its properties (unique paths, depths) are heavily used.
  • →Big-O notation — To analyze runtime and space like O(n + m) and O((n) log n) for LCA preprocessing.

Detailed Explanation

Tap terms for definitions

01Overview

Imagine taking a complicated undirected graph and exposing its fragile spots—those vertices whose removal would tear the graph apart. A Block-Cut Tree (also called a BC-tree) is a structured summary that highlights exactly where a graph can break and how its robust regions are glued together. It replaces the original graph with a bipartite tree whose nodes are either blocks (biconnected components) or articulation points (cut vertices). An edge connects an articulation point to each block that contains it. Non-articulation vertices live inside exactly one block and do not appear as separate nodes in the tree. This transformation is powerful because trees are easy to compute with: they have unique paths, and typical queries—like how many articulation points separate two vertices—become path queries solvable with LCA (Lowest Common Ancestor) in logarithmic time per query. You build the Block-Cut Tree in linear time using Tarjan’s DFS to compute discovery times and low-link values. When the DFS finds a point where a subtree cannot reach above its parent, it has discovered a biconnected component, which becomes a block node in the BC-tree. Overall, the Block-Cut Tree provides a clean and efficient way to reason about vertex connectivity, failure points, and separations in large graphs.

02Intuition & Analogies

Think of a city map: neighborhoods (blocks) are internal areas with many side streets so that if you close one intersection, you can still get around inside the neighborhood. Intersections that connect neighborhoods are fragile chokepoints—if one of these special intersections (articulation points) is closed, entire neighborhoods can become cut off from each other. The Block-Cut Tree is like compressing each robust neighborhood into a bubble and keeping every critical intersection as its own node. Then you draw a line from a bubble to each critical intersection that touches it. The result is a two-layer network: bubble nodes (blocks) and intersection nodes (articulation points). This new network is always a forest (a collection of trees), which is much simpler than the street map you started with. Any route between two addresses in the original city corresponds to a unique path in this forest. If your path crosses K special intersections, it means there are K articulation points along any route between the two addresses in the original city. Why is this useful? Trees give you certainty: there is exactly one route between two nodes, so you can count how many critical intersections lie on it—no ambiguity. Also, if two addresses are inside the same bubble, they are safe from single-intersection closures (they are in the same biconnected component). If they lie in different bubbles, some articulation point must separate them. That’s why the Block-Cut Tree is a go-to tool for vertex-connectivity reasoning and fast query processing.

03Formal Definition

Let G = (V, E) be a finite undirected graph. A vertex v ∈ V is an articulation point (cut vertex) if removing v (and incident edges) strictly increases the number of connected components of G. A biconnected component (block) is a maximal induced subgraph B = (, ) with ≥ 2 such that for all x ∈ , B − x remains connected; equivalently, B has no articulation vertex internal to it. In simple graphs, a bridge edge forms a block of size two if it is not part of any cycle. The Block-Cut Tree T of G is a bipartite graph with two types of nodes: B-nodes, one for each biconnected component, and A-nodes, one for each articulation point. There is an edge (a, b) in T between an articulation node a and a block node b if and only if the corresponding articulation vertex belongs to that biconnected component in G. Every non-articulation vertex belongs to exactly one block and has no separate node in T. For each connected component of G, the corresponding induced subgraph in T is a tree; thus T is a forest overall. The construction is unique up to the naming of nodes. Tarjan’s algorithm identifies articulation points and biconnected components in O( + ) time using a DFS traversal with discovery times tin[u] and low-link values low[u], and a stack of edges to extract each block when a low-link threshold is met.

04When to Use

Use a Block-Cut Tree when you need to reason about vertex connectivity instead of edge connectivity. Typical scenarios include:

  • Fast vertex-separation queries: How many articulation points separate u and v? On the BC-tree this reduces to counting articulation nodes on the unique path between the representatives of u and v, which is doable with LCA and prefix sums.
  • Testing 2-vertex-connectivity: Are u and v in the same biconnected component? This is equivalent to checking whether they share a block in the decomposition (intersection of their block memberships).
  • Failure analysis and robustness: If a vertex fails, how many components does the graph split into? For a connected component, the answer for an articulation vertex equals its degree in the BC-tree.
  • Preprocessing for more advanced tasks: Many problems on CF/ICPC transform an undirected graph into a BC-tree and then apply tree techniques (binary lifting, heavy-light decomposition, centroid decomposition) to answer large batches of path or reachability queries under single-vertex failures. Avoid BC-trees when you need edge-connectivity; in that case use bridge trees or 2-edge-connected component decomposition instead. Also, if your graph is directed, the BC-tree does not apply; consider strongly connected components or dominator trees.

⚠️Common Mistakes

  • Confusing edge- vs vertex-biconnectivity: Bridges and 2-edge-connected components are not what BC-trees capture. BC-trees are about vertices (articulation points) and biconnected components, not bridges alone.
  • Forgetting that the BC structure is a forest: If the original graph is disconnected, the BC-tree is a forest. LCA preprocessing and traversals must account for multiple roots.
  • Building wrong edges: In the BC-tree, connect only articulation nodes to block nodes that contain them. Do not add nodes for non-articulation vertices and do not connect block-to-block or articulation-to-articulation.
  • Mishandling DFS stack for components: When extracting a biconnected component, you must pop all edges up to and including the triggering tree edge (u, v). Missing edges or mixing tree/back edges breaks correctness.
  • Root articulation condition: The DFS root is an articulation point if and only if it has at least two DFS children. Non-root u is an articulation point if there exists a child v with low[v] ≥ tin[u]. Mixing these up is a common bug.
  • Incorrect path counting on BC-tree: If you count articulation nodes on a path using prefix sums, remember whether endpoints should be included. A safe pattern is sum(u) + sum(v) − 2·sum(lca) + isArt(lca), then subtract endpoints if you want strict internal nodes.
  • Ignoring multiedges/self-loops: Self-loops don’t affect articulation points but can confuse low-link handling if not filtered. Parallel edges may create cycles of length 2; ensure your algorithm treats them correctly.

Key Formulas

Low-link value

Explanation: The low-link of u is the smallest discovery time reachable from u by going down zero or more tree edges, then possibly one back edge. It drives component extraction and articulation detection.

Articulation test

Explanation: A root splits the DFS tree if it has two or more children. Any non-root u is articulation if some subtree cannot reach an ancestor of u, i.e., low[v] >= tin[u].

Tree distance

Explanation: In any rooted tree T, the number of edges on the unique path between x and y equals the sum of depths minus twice the LCA depth. Used on the Block-Cut Tree.

Articulation count on path

Explanation: If S[v] is the prefix sum of weights w (1 on articulation nodes, 0 on block nodes) from root to v, then A(x,y) counts articulation nodes on the path x–y (including the LCA if it is an articulation). Subtract w(x) and w(y) to exclude endpoints.

BC-tree size

Explanation: The Block-Cut Tree has one node per articulation and one per block. Each incidence between an articulation point and a block becomes an edge in the BC-tree.

Same biconnected component criterion

Explanation: By definition of blocks as maximal biconnected subgraphs, sharing a block means two-vertex connectivity between u and v.

Linear-time decomposition

Explanation: Tarjan’s DFS, component extraction, and BC-tree construction each process vertices and edges a constant number of times, yielding overall linear time.

Complexity Analysis

Let n = and m = for the original undirected graph. Tarjan’s DFS computes tin[u] and low[u] for every vertex u and considers each edge at most twice (once per direction), so the DFS is O(n + m). Each edge is pushed to and popped from the component stack at most once; the total stack work is O(m). Extracting a biconnected component involves popping a contiguous block of edges and collecting their endpoints; across all components, the total number of pushed/popped edges is O(m), and with token-based marking the total endpoint insertions is O(m) as well, preserving linear time. Let A be the number of articulation points and B the number of blocks. Constructing the Block-Cut Tree requires visiting every component and, for each vertex it contains, possibly adding one BC edge if the vertex is an articulation. The total number of such incidences is exactly , which is O(n + m) in the worst case (bounded by total appearances of endpoints during component extraction), so building BC adjacency is O(A + B + ) = O(n + m). For path queries on the BC-tree, binary lifting preprocessing takes O((A + B) log(A + B)) time and O((A + B) log(A + B)) space for the ancestor table. Each LCA or weighted path-sum query then runs in O(log(A + B)). If you only need to test whether two vertices share a block, an intersection of their (typically small) block-membership lists runs in O(de(u) + de(v)), where de(x) is the number of blocks containing x (1 for non-articulation vertices). The overall space usage is O(n + m): original graph O(n + m), stacks and arrays O(n), component storage linear in total edge appearances, and BC-tree O(A + B + ).

Code Examples

Build a Block-Cut Tree: extract blocks and articulation points
1#include <bits/stdc++.h>
2using namespace std;
3
4struct BlockCutTree {
5    int n;                          // original number of vertices [0..n-1]
6    vector<vector<int>> g;          // original graph
7    vector<int> tin, low;           // discovery times and low-link values
8    int timer = 0;
9    vector<pair<int,int>> st;       // stack of edges for component extraction
10    vector<char> isArt;             // articulation flags in original graph
11
12    // temporary token marking for collecting unique vertices per component
13    vector<int> seenToken;          
14    int curToken = 1;
15
16    vector<vector<int>> comps;      // list of vertices per biconnected component (block)
17    vector<vector<int>> compsOfV;   // for each original vertex, list of block indices containing it
18
19    // Block-Cut Tree (BC-tree) data
20    int A = 0, B = 0;               // counts: articulation nodes, block nodes
21    vector<int> idArt;              // map original vertex -> articulation node id in BC-tree (or -1)
22    vector<vector<int>> bct;        // BC-tree adjacency (size = A + B)
23
24    // LCA / path helpers on BC-tree
25    vector<int> depth, prefArt, nodeWeight;  // weights: 1 for articulation node, 0 for block node
26    vector<vector<int>> up;         // binary lifting table
27
28    BlockCutTree(int n=0): n(n) {
29        g.assign(n, {});
30    }
31
32    void add_edge(int u, int v) {
33        g[u].push_back(v);
34        g[v].push_back(u);
35    }
36
37    void dfs(int u, int p) {
38        tin[u] = low[u] = ++timer;
39        int childCount = 0;
40        for (int v : g[u]) {
41            if (v == p) continue;
42            if (tin[v] == 0) {
43                st.emplace_back(u, v);
44                dfs(v, u);
45                low[u] = min(low[u], low[v]);
46                if (low[v] >= tin[u]) {
47                    if (p != -1) isArt[u] = 1; // non-root articulation condition
48                    // extract one biconnected component by popping edges until (u,v)
49                    vector<int> comp;
50                    ++curToken;
51                    while (!st.empty()) {
52                        auto e = st.back(); st.pop_back();
53                        if (seenToken[e.first] != curToken) {
54                            seenToken[e.first] = curToken;
55                            comp.push_back(e.first);
56                        }
57                        if (seenToken[e.second] != curToken) {
58                            seenToken[e.second] = curToken;
59                            comp.push_back(e.second);
60                        }
61                        if (e.first == u && e.second == v) break;
62                    }
63                    comps.push_back(comp);
64                }
65                childCount++;
66            } else if (tin[v] < tin[u]) {
67                // back edge to an ancestor
68                st.emplace_back(u, v);
69                low[u] = min(low[u], tin[v]);
70            }
71        }
72        if (p == -1 && childCount >= 2) isArt[u] = 1; // root articulation condition
73    }
74
75    void build() {
76        tin.assign(n, 0); low.assign(n, 0);
77        isArt.assign(n, 0);
78        seenToken.assign(n, 0);
79        timer = 0; st.clear(); comps.clear();
80        compsOfV.assign(n, {});
81
82        for (int i = 0; i < n; ++i) if (tin[i] == 0) dfs(i, -1);
83
84        // Fill membership lists (which blocks contain which vertices)
85        for (int i = 0; i < (int)comps.size(); ++i) {
86            for (int v : comps[i]) compsOfV[v].push_back(i);
87        }
88        for (int v = 0; v < n; ++v) sort(compsOfV[v].begin(), compsOfV[v].end());
89
90        // Map articulation vertices to BC-tree A-nodes
91        idArt.assign(n, -1);
92        for (int v = 0; v < n; ++v) if (isArt[v]) idArt[v] = A++;
93        B = (int)comps.size();
94        bct.assign(A + B, {});
95
96        // Connect articulation nodes to their blocks
97        for (int i = 0; i < B; ++i) {
98            int blockNode = A + i;
99            for (int v : comps[i]) if (isArt[v]) {
100                int aNode = idArt[v];
101                bct[aNode].push_back(blockNode);
102                bct[blockNode].push_back(aNode);
103            }
104        }
105
106        // Prepare LCA helpers (optional, used in other examples)
107        int N = A + B;
108        nodeWeight.assign(N, 0);
109        for (int i = 0; i < A; ++i) nodeWeight[i] = 1; // articulation nodes weight 1
110        depth.assign(N, 0);
111        prefArt.assign(N, 0);
112        int LOG = (N == 0 ? 1 : 32 - __builtin_clz(N));
113        up.assign(LOG, vector<int>(N, 0));
114
115        vector<int> vis(N, 0);
116        function<void(int,int)> dfs_bct = [&](int u, int p) {
117            vis[u] = 1; up[0][u] = (p == -1 ? u : p);
118            for (int k = 1; k < LOG; ++k) up[k][u] = up[k-1][ up[k-1][u] ];
119            for (int v : bct[u]) if (v != p) {
120                depth[v] = depth[u] + 1;
121                prefArt[v] = prefArt[u] + nodeWeight[v];
122                dfs_bct(v, u);
123            }
124        };
125        for (int i = 0; i < N; ++i) if (!vis[i]) {
126            depth[i] = 0; prefArt[i] = nodeWeight[i];
127            dfs_bct(i, -1);
128        }
129    }
130};
131
132int main() {
133    ios::sync_with_stdio(false);
134    cin.tie(nullptr);
135
136    int n, m;
137    if (!(cin >> n >> m)) {
138        // Example usage if no input: a graph with two triangles sharing a vertex 2
139        n = 5; m = 6;
140        BlockCutTree BCT(n);
141        vector<pair<int,int>> E = {{0,1},{1,2},{2,0},{2,3},{3,4},{4,2}};
142        for (auto [u,v] : E) BCT.add_edge(u,v);
143        BCT.build();
144
145        cout << "Articulation points: ";
146        for (int v = 0; v < n; ++v) if (BCT.isArt[v]) cout << v << ' ';
147        cout << "\n";
148        cout << "Number of blocks: " << BCT.B << "\n";
149        for (int i = 0; i < BCT.B; ++i) {
150            cout << "Block " << i << ": ";
151            for (int v : BCT.comps[i]) cout << v << ' ';
152            cout << "\n";
153        }
154        cout << "BC-tree nodes (A+B): " << (BCT.A + BCT.B) << ", edges: ";
155        long long ecount = 0; for (auto &adj : BCT.bct) ecount += adj.size();
156        cout << ecount/2 << "\n";
157        return 0;
158    }
159
160    BlockCutTree BCT(n);
161    for (int i = 0; i < m; ++i) {
162        int u, v; cin >> u >> v; // assume 0-indexed input
163        BCT.add_edge(u, v);
164    }
165    BCT.build();
166
167    cout << "Articulation points (count=" << count(BCT.isArt.begin(), BCT.isArt.end(), 1) << "): ";
168    for (int v = 0; v < n; ++v) if (BCT.isArt[v]) cout << v << ' ';
169    cout << "\n";
170
171    cout << "Blocks: " << BCT.B << "\n";
172    for (int i = 0; i < BCT.B; ++i) {
173        cout << "Block " << i << " contains: ";
174        for (int v : BCT.comps[i]) cout << v << ' ';
175        cout << "\n";
176    }
177
178    cout << "BC-tree has nodes (A+B) = " << (BCT.A + BCT.B) << ", edges = ";
179    long long ecount = 0; for (auto &adj : BCT.bct) ecount += adj.size();
180    cout << ecount/2 << "\n";
181
182    return 0;
183}
184

This program builds the Block-Cut Tree of an undirected graph using Tarjan’s algorithm. It extracts all biconnected components (blocks), marks articulation points, and connects articulation nodes to block nodes to form the BC-tree. It also prepares LCA-related arrays for later path queries (used in the next examples).

Time: O(n + m) for building the BC-treeSpace: O(n + m) overall
Queries on the Block-Cut Tree: same block? number of articulation points between two vertices
1#include <bits/stdc++.h>
2using namespace std;
3
4struct BlockCutTree {
5    int n; vector<vector<int>> g; vector<int> tin, low; int timer=0; vector<pair<int,int>> st;
6    vector<char> isArt; vector<int> seenToken; int curToken=1; vector<vector<int>> comps, compsOfV;
7    int A=0, B=0; vector<int> idArt; vector<vector<int>> bct; vector<int> rep;
8    vector<int> depth, prefArt, nodeWeight; vector<vector<int>> up;
9
10    BlockCutTree(int n=0): n(n) { g.assign(n, {}); }
11    void add_edge(int u, int v){ g[u].push_back(v); g[v].push_back(u);}    
12
13    void dfs(int u, int p){
14        tin[u]=low[u]=++timer; int child=0;
15        for(int v: g[u]){
16            if(v==p) continue;
17            if(tin[v]==0){
18                st.emplace_back(u,v); dfs(v,u); low[u]=min(low[u], low[v]);
19                if(low[v] >= tin[u]){
20                    if(p!=-1) isArt[u]=1;
21                    vector<int> comp; ++curToken;
22                    while(!st.empty()){
23                        auto e=st.back(); st.pop_back();
24                        if(seenToken[e.first]!=curToken){seenToken[e.first]=curToken; comp.push_back(e.first);}            
25                        if(seenToken[e.second]!=curToken){seenToken[e.second]=curToken; comp.push_back(e.second);}          
26                        if(e.first==u && e.second==v) break;
27                    }
28                    comps.push_back(comp);
29                }
30                child++;
31            } else if(tin[v] < tin[u]){
32                st.emplace_back(u,v); low[u]=min(low[u], tin[v]);
33            }
34        }
35        if(p==-1 && child>=2) isArt[u]=1;
36    }
37
38    void build(){
39        tin.assign(n,0); low.assign(n,0); isArt.assign(n,0); seenToken.assign(n,0);
40        timer=0; st.clear(); comps.clear(); compsOfV.assign(n,{});
41        for(int i=0;i<n;++i) if(tin[i]==0) dfs(i,-1);
42        for(int i=0;i<(int)comps.size();++i) for(int v: comps[i]) compsOfV[v].push_back(i);
43        for(int v=0; v<n; ++v) sort(compsOfV[v].begin(), compsOfV[v].end());
44        idArt.assign(n,-1); A=0; for(int v=0; v<n; ++v) if(isArt[v]) idArt[v]=A++;
45        B=(int)comps.size(); bct.assign(A+B,{});
46        for(int i=0;i<B;++i){ int blockNode=A+i; for(int v: comps[i]) if(isArt[v]){ int a=idArt[v]; bct[a].push_back(blockNode); bct[blockNode].push_back(a);} }
47        // map each original vertex to a representative in BC-tree
48        rep.assign(n, -1);
49        for(int v=0; v<n; ++v){ if(isArt[v]) rep[v]=idArt[v]; else if(!compsOfV[v].empty()) rep[v]=A + compsOfV[v][0]; }
50        // LCA prep
51        int N=A+B; nodeWeight.assign(N,0); for(int i=0;i<A;++i) nodeWeight[i]=1;
52        int LOG = (N==0?1:32-__builtin_clz(N)); up.assign(LOG, vector<int>(N,0)); depth.assign(N,0); prefArt.assign(N,0);
53        vector<int> vis(N,0);
54        function<void(int,int)> dfs2 = [&](int u, int p){
55            vis[u]=1; up[0][u]=(p==-1?u:p);
56            for(int k=1;k<LOG;++k) up[k][u]=up[k-1][ up[k-1][u] ];
57            for(int v: bct[u]) if(v!=p){ depth[v]=depth[u]+1; prefArt[v]=prefArt[u]+nodeWeight[v]; dfs2(v,u);} };
58        for(int i=0;i<N;++i) if(!vis[i]){ depth[i]=0; prefArt[i]=nodeWeight[i]; dfs2(i,-1);}        
59    }
60
61    int lca(int a, int b){
62        if(a==-1||b==-1) return -1; if(depth[a]<depth[b]) swap(a,b);
63        int LOG=up.size(); int d=depth[a]-depth[b];
64        for(int k=0;k<LOG;++k) if(d&(1<<k)) a=up[k][a];
65        if(a==b) return a;
66        for(int k=LOG-1;k>=0;--k) if(up[k][a]!=up[k][b]){ a=up[k][a]; b=up[k][b]; }
67        return up[0][a];
68    }
69
70    // Count articulation nodes on the BC-tree path between representatives of u and v.
71    // If excludeEndpoints=true, do not count articulation nodes that are rep[u] or rep[v].
72    int countArticulationsBetween(int u, int v, bool excludeEndpoints=true){
73        int x=rep[u], y=rep[v]; if(x==-1||y==-1) return 0; int L=lca(x,y); if(L==-1) return 0;
74        int sum = prefArt[x] + prefArt[y] - 2*prefArt[L] + ( (L < A) ? 1 : 0 );
75        if(excludeEndpoints){ if(x < A) sum--; if(y < A) sum--; }
76        return sum;
77    }
78
79    bool sameBlock(int u, int v){
80        auto &a = compsOfV[u]; auto &b = compsOfV[v];
81        int i=0,j=0; while(i<(int)a.size() && j<(int)b.size()){
82            if(a[i]==b[j]) return true; if(a[i]<b[j]) ++i; else ++j;
83        }
84        return false;
85    }
86};
87
88int main(){
89    ios::sync_with_stdio(false);
90    cin.tie(nullptr);
91
92    int n,m; cin>>n>>m; BlockCutTree BCT(n);
93    for(int i=0;i<m;++i){int u,v;cin>>u>>v; BCT.add_edge(u,v);} // 0-indexed
94    BCT.build();
95
96    int q; cin>>q;
97    // Query types:
98    // 1 u v : print YES if u and v are in the same biconnected component, else NO
99    // 2 u v : print the number of articulation points strictly between u and v
100    while(q--){
101        int t,u,v; cin>>t>>u>>v;
102        if(t==1){ cout << (BCT.sameBlock(u,v)?"YES":"NO") << "\n"; }
103        else if(t==2){ cout << BCT.countArticulationsBetween(u,v,true) << "\n"; }
104    }
105    return 0;
106}
107

This program builds the Block-Cut Tree, maps every original vertex to a representative BC-node (articulation vertex -> articulation node; non-articulation vertex -> its unique block), and supports two queries: whether two vertices lie in the same biconnected component (intersection of their component lists) and how many articulation points lie strictly between them (path sum on the BC-tree using LCA and prefix sums).

Time: Preprocessing O(n + m) for BC-tree + O((A+B) log(A+B)) for LCA; each query O(log(A+B)) (count) or O(deg(u)+deg(v)) (same-block)Space: O(n + m + (A+B) log(A+B))
Articulation impact: components created by removing each articulation vertex
1#include <bits/stdc++.h>
2using namespace std;
3
4struct BlockCutTree {
5    int n; vector<vector<int>> g; vector<int> tin, low; int timer=0; vector<pair<int,int>> st;
6    vector<char> isArt; vector<int> seenToken; int curToken=1; vector<vector<int>> comps;
7    int A=0,B=0; vector<int> idArt; vector<vector<int>> bct;
8
9    BlockCutTree(int n=0): n(n){ g.assign(n,{}); }
10    void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
11    void dfs(int u,int p){
12        tin[u]=low[u]=++timer; int child=0;
13        for(int v: g[u]){
14            if(v==p) continue;
15            if(tin[v]==0){
16                st.emplace_back(u,v); dfs(v,u); low[u]=min(low[u],low[v]);
17                if(low[v] >= tin[u]){
18                    if(p!=-1) isArt[u]=1; vector<int> comp; ++curToken;
19                    while(!st.empty()){
20                        auto e=st.back(); st.pop_back();
21                        if(seenToken[e.first]!=curToken){seenToken[e.first]=curToken; comp.push_back(e.first);}            
22                        if(seenToken[e.second]!=curToken){seenToken[e.second]=curToken; comp.push_back(e.second);}          
23                        if(e.first==u && e.second==v) break;
24                    }
25                    comps.push_back(comp);
26                }
27                child++;
28            } else if(tin[v] < tin[u]){ st.emplace_back(u,v); low[u]=min(low[u], tin[v]); }
29        }
30        if(p==-1 && child>=2) isArt[u]=1;
31    }
32    void build(){
33        tin.assign(n,0); low.assign(n,0); isArt.assign(n,0); seenToken.assign(n,0);
34        timer=0; st.clear(); comps.clear();
35        for(int i=0;i<n;++i) if(tin[i]==0) dfs(i,-1);
36        idArt.assign(n,-1); for(int v=0; v<n; ++v) if(isArt[v]) idArt[v]=A++;
37        B=(int)comps.size(); bct.assign(A+B,{});
38        for(int i=0;i<B;++i){ int blockNode=A+i; for(int v: comps[i]) if(isArt[v]){ int a=idArt[v]; bct[a].push_back(blockNode); bct[blockNode].push_back(a);} }
39    }
40};
41
42int main(){
43    ios::sync_with_stdio(false);
44    cin.tie(nullptr);
45
46    int n,m; cin>>n>>m; BlockCutTree BCT(n);
47    for(int i=0;i<m;++i){int u,v;cin>>u>>v; BCT.add_edge(u,v);} // 0-indexed
48    BCT.build();
49
50    // For each articulation vertex v, the number of connected components in its original connected component
51    // after removing v equals deg_BCT(v), i.e., the degree of its articulation node in the BC-tree.
52    vector<int> degIfRemoved(n, 1); // default 1 means 'no split' for non-articulation vertices (component count stays the same per connected component)
53    for(int v=0; v<n; ++v){
54        if(BCT.isArt[v]){
55            int a = BCT.idArt[v];
56            degIfRemoved[v] = (int)BCT.bct[a].size();
57        } else {
58            degIfRemoved[v] = 1; // removing a non-articulation vertex does not split its connected component
59        }
60    }
61
62    int q; cin>>q; // answer queries: for a vertex v, how many components appear in its connected component after removal
63    while(q--){
64        int v; cin>>v;
65        cout << degIfRemoved[v] << "\n";
66    }
67    return 0;
68}
69

This program computes, for each vertex v, how many connected components its original connected component splits into after removing v. For articulation vertices, this equals their degree in the BC-tree; for non-articulation vertices, the answer is 1 (no split). This showcases a direct structural interpretation of the BC-tree.

Time: O(n + m) preprocessing; each query O(1)Space: O(n + m)