⚙️AlgorithmAdvanced

Biconnected Components

Key Points

•
A biconnected component (block) is a maximal subgraph where removing any single vertex keeps it connected.
•
You can find all biconnected components in O(n + m) time with one DFS using Tarjan’s low-link values and an edge stack.
•
An articulation point is a vertex whose removal increases the number of connected components; it sits between multiple blocks.
•
Two vertices are 2-vertex-connected if and only if they belong to a common biconnected component.
•
The edges of a biconnected component with at least three vertices are covered by simple cycles; bridges form single-edge blocks.
•
The block-cut tree is a bipartite tree connecting block nodes to articulation-point nodes and summarizes the graph’s 2-vertex structure.
•
Cycle decomposition per block can be obtained by a DFS-based cycle basis of size E - V + 1 inside that block.
•
Typical applications include robustness analysis, 2-vertex-connected queries, cycle decomposition, and preprocessing for advanced graph problems.

Prerequisites

→Depth-First Search (DFS) — Tarjan’s algorithm is a single DFS; understanding tree edges, back-edges, and recursion is essential.
→Graph representations (adjacency lists) — Efficient storage and traversal in O(n + m) time requires adjacency lists.
→Stacks and recursion — The algorithm maintains an edge stack and typically uses recursive DFS.
→Articulation points and bridges — Knowledge of cut vertices and bridges clarifies what blocks represent and how to detect them.
→Tarjan’s low-link technique — Low-link values are the core mechanism for detecting blocks and articulation points.
→Paths and cycles in graphs — Understanding 2-vertex connectivity and cycle decomposition depends on basic path/cycle concepts.
→Asymptotic analysis — To reason about O(n + m) preprocessing and per-query costs.

Detailed Explanation

Tap terms for definitions

01Overview

Hook: Imagine a city’s road network that must remain navigable even if one intersection is closed. Which areas can survive any single-vertex closure? Concept: These resilient regions are called biconnected components (also known as blocks). Formally, a biconnected component is a maximal subgraph with no articulation point: removing any single vertex from it does not disconnect the subgraph. In an undirected graph, blocks partition the edges (not necessarily the vertices), and articulation points are the shared vertices "gluing" multiple blocks together. We can reveal this structure efficiently with a single depth-first search (DFS) using Tarjan’s low-link values, maintaining a stack of edges that belong to the current DFS frontier. When the DFS detects that a subtree cannot reach above its parent (via back-edges), it completes a block and pops its edges from the stack. Example: In a graph shaped like two cycles connected at one vertex, that shared vertex is an articulation point. Each cycle is a separate biconnected component, and the common vertex belongs to both blocks. Finding these blocks helps answer queries like "Do u and v remain connected after removing any one vertex?" (answer: yes if they are in a common block) and also enables a cycle decomposition of the graph.

02Intuition & Analogies

Think of a graph as a network of rooms (vertices) connected by hallways (edges). A biconnected component is a cluster of rooms where no single room is a critical chokepoint; even if one room is closed, you can still walk between any two remaining rooms in that cluster by detouring through alternative hallways. The chokepoint rooms that split clusters apart are articulation points—like key intersections where multiple building wings meet. How do we discover these clusters? DFS is like exploring the building with a string: when you enter a hallway, you push it onto a stack. If you find a staircase back to a higher floor (a back-edge to an ancestor), you’ve discovered redundancy—alternate routes that avoid some rooms. But if a whole wing (a subtree) cannot climb back above the connecting room, then that connecting room is a chokepoint for that wing; all hallways explored since entering that wing form one tightly knit cluster. By popping the edge stack up to the connector edge, you peel off exactly the hallways that belong to that cluster. Repeat this process for every wing. The result is a set of blocks (redundant zones) tied together by articulation points (bottlenecks). For queries, asking whether two rooms are robustly connected despite any one room’s closure is equivalent to asking: do they share a common redundant zone (block) with multiple independent ways around? For cycles, each nontrivial block is woven by cycles; within it, edges are supported by circular routes rather than dangling corridors.

03Formal Definition

Let G = (V, E) be a finite, undirected, simple graph. A subgraph H = (

V_{H}

E_{H}

) is biconnected if

∣ V_{H} ∣

≥ 2 and for all x ∈

V_{H}

, the graph H − x is connected. A biconnected component (block) of G is a maximal biconnected subgraph with respect to edge inclusion. Edges in G are uniquely partitioned among blocks; vertices can belong to multiple blocks (precisely the articulation points). An articulation point is a vertex a ∈ V such that the number of connected components of G − a is greater than the number of connected components of G. Tarjan’s DFS characterizes articulation points and blocks using discovery times disc[u] and low-link values low[u]. For an undirected graph, low[u] is the minimum disc reachable from u by either (1) staying in u, (2) taking one back-edge, or (3) traversing zero or more tree edges then a back-edge. A vertex u (non-root) is an articulation point if it has a child v in the DFS tree with low[v] ≥ disc[u]. The root of the DFS tree is an articulation point if it has at least two children. Each time low[v] ≥ disc[u] holds, the set of edges on the DFS stack up to edge (u, v) forms one biconnected component.

04When to Use

Use biconnected components when you need to understand vertex-robust connectivity. Typical scenarios: (1) Reliability analysis: Determine critical intersections (articulations) whose failure disconnects the network, and identify robust zones (blocks) safe against any single vertex failure. (2) 2-vertex-connected queries: To answer “Do u and v remain connected after removing any one vertex?”, preprocess the graph into blocks; u and v are 2-vertex-connected iff they belong to a common block. (3) Cycle decomposition: Inside each nontrivial block, edges form cycles; you can generate a cycle basis of size E − V + 1 per block to analyze redundancy (useful in algorithms involving flows, electrical circuits, or planar embeddings). (4) Graph compression: Build the block-cut tree—a bipartite tree of block nodes and articulation nodes—which simplifies many problems (e.g., counting articulation points on paths, dynamic programming over the tree). (5) Contest applications around CF 1800–2200: problems asking to count blocks, check robustness of pairs, remove minimal vertices to disconnect pairs, or compute properties that are easier on the block-cut tree.

⚠️Common Mistakes

• Confusing edge biconnectivity with vertex biconnectivity: Bridges relate to edge biconnectivity; here we handle vertex biconnectivity. In this setting, a block can be a single edge (if it’s a bridge), but nontrivial blocks (|V| ≥ 3) have no articulation points inside. • Mishandling back-edges in DFS: In an undirected graph, you must only push a back-edge (u, v) when disc[v] < disc[u] (v is an ancestor). Pushing edges to already discovered descendants creates duplicates or wrong components. • Forgetting the DFS root rule: The root is an articulation point only if it has at least two DFS-tree children; applying the non-root rule to the root is incorrect. • Not popping leftover edges after finishing a connected component: After DFS finishes a root, all remaining edges on the stack form one last block; forgetting this loses components. • Assuming vertices are partitioned among blocks: Edges are partitioned; vertices may appear in multiple blocks (articulation points). • Misanswering 2-vertex-connected queries: Two vertices are 2-vertex-connected iff they share at least one common block (endpoints may include an articulation vertex). • Building an incorrect block-cut tree: Only articulation vertices become articulation nodes; non-articulation vertices do not appear as separate nodes in the block-cut tree. • Performance pitfalls: Using per-component hash sets can be fine, but if you need to scale, prefer reusing mark arrays or integer timestamps to avoid O(k log k) overheads.

Key Formulas

Low-link definition

l o w [u] = min (d i sc [u], (u, w) back-edge min d i sc [w], v \in children (u) min l o w [v])

Explanation: The lowest discovery time reachable from u by staying at u, taking one back-edge, or going down the DFS tree and then back up via a back-edge. It captures whether u’s subtree can connect above u.

Articulation criterion (non-root)

u is an articulation (non-root) ⟺ \exists v \in children (u) : l o w [v] \geq d i sc [u]

Explanation: If a child subtree cannot reach ancestors of u, removing u disconnects that subtree from the rest. This flags u as a cut vertex.

Articulation criterion (root)

u is an articulation (root) ⟺ # children (u) \geq 2

Explanation: The root is a cut vertex if it has two or more DFS-tree children, because removing it separates their subtrees.

Block extraction rule

l o w [v] \geq d i sc [u] \Rightarrow edges on the stack up to (u, v) form one block

Explanation: When a child subtree cannot climb above u, all edges explored since entering that subtree belong to one biconnected component and are popped from the edge stack.

Time complexity

T (n, m) = O (n + m)

Explanation: Each vertex and edge is processed a constant number of times by the DFS and stack operations, so the algorithm runs linear in the graph size.

Cycle rank (cyclomatic number)

β = m - n + c

Explanation: For an undirected graph with n vertices, m edges, and c connected components, $β$ gives the size of a cycle basis. Inside a connected block, it reduces to E - V + 1.

Pairwise 2-vertex-connectivity

u and v are 2-vertex-connected ⟺ \exists block B : u, v \in B

Explanation: By Menger’s theorem and the structure of blocks, two vertices share two internally vertex-disjoint paths exactly when they lie in a common block.

Block-cut tree property

Block-cut graph is a tree if G is connected

Explanation: Connecting each block node to its articulation points produces a bipartite acyclic graph; in a connected G, this graph is a tree summarizing how blocks are glued together.

Bridge test (for reference)

(u, v) is a bridge ⟺ l o w [v] > d i sc [u]

Explanation: If a child v cannot reach u or any ancestor of u, removing edge (u,v) disconnects v’s subtree from the rest, so it is a bridge (a single-edge block).

Complexity Analysis

The standard Tarjan-based algorithm for biconnected components runs in linear time relative to the size of the input graph. Specifically, for an undirected graph with n vertices and m edges, the DFS visits each vertex exactly once and considers each undirected edge a constant number of times (once from each endpoint), yielding O(n + m) time. Pushing and popping edges on the stack also occurs at most once per edge, so all stack operations are amortized O(1) per edge. Constructing each block’s vertex list from the popped edges requires touching only the edges in that block; across all blocks this is still O(m). Building the block-cut tree connects each block node to articulation points it contains; the total number of such incidences is O(m) in the worst case, so this step is also linear. Space usage is O(n + m): adjacency lists store O(m) edges; arrays for discovery time, low-link, parent, and articulation flags use O(n); the edge stack holds at most O(m) edges at any time. Additional structures such as “blocks per vertex” vectors sum to O(m) total, because each edge contributes to exactly one block while a vertex may appear in multiple blocks only as an articulation (bounded by its degree). Answering a single 2-vertex-connected query by intersecting the small lists of blocks per vertex runs in O(de

g_{B}

(u) + de

g_{B}

(v)), where de

g_{B}

(x) is the number of blocks containing x (often small). If many queries are required, one can further optimize intersections using marks or bitsets while retaining near-linear preprocessing.

Code Examples

Tarjan DFS to find biconnected components and articulation points (edge stack method)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct BiconnectedComponents {
5     int n, timer;
6     vector<vector<int>> g;                  // adjacency list (0-indexed)
7     vector<int> disc, low, parent;         // discovery time, low-link, parent
8     vector<bool> isArt;                    // articulation flags
9     vector<pair<int,int>> st;              // stack of edges
10 
11     // Results: each block as list of edges and list of vertices
12     vector<vector<pair<int,int>>> blocks_edges;  // edges in each block
13     vector<vector<int>> blocks_vertices;         // unique vertices in each block
14 
15     BiconnectedComponents(int n): n(n), timer(0) {
16         g.assign(n, {});
17         disc.assign(n, 0);
18         low.assign(n, 0);
19         parent.assign(n, -1);
20         isArt.assign(n, false);
21     }
22 
23     void addEdge(int u, int v) {
24         // undirected simple graph
25         g[u].push_back(v);
26         g[v].push_back(u);
27     }
28 
29     void dfs(int u) {
30         disc[u] = low[u] = ++timer;
31         int childCount = 0;
32         for (int v : g[u]) {
33             if (v == parent[u]) continue; // skip the tree edge to parent
34             if (disc[v] == 0) {
35                 // Tree edge (u, v)
36                 parent[v] = u;
37                 st.push_back({u, v});
38                 ++childCount;
39                 dfs(v);
40                 low[u] = min(low[u], low[v]);
41 
42                 // If v's subtree cannot reach an ancestor of u, we found a block
43                 if (low[v] >= disc[u]) {
44                     if (parent[u] != -1 || childCount > 1) isArt[u] = true;
45 
46                     vector<pair<int,int>> edges;
47                     // Pop until (u, v) is popped
48                     while (!st.empty()) {
49                         auto e = st.back(); st.pop_back();
50                         edges.push_back(e);
51                         if ((e.first == u && e.second == v) ||
52                             (e.first == v && e.second == u)) break;
53                     }
54                     // Collect unique vertices from these edges
55                     vector<int> verts;
56                     verts.reserve(edges.size() * 2);
57                     // Use a temporary mark array via timestamp to avoid O(log n) set
58                     static vector<int> mark(1, -1), seen(1, 0);
59                     if ((int)mark.size() < n) { mark.assign(n, -1); seen.assign(n, 0); }
60                     int seen_id = u + timer; // any changing id works; uniqueness not required globally
61                     for (auto &e : edges) {
62                         if (mark[e.first] != seen_id) { mark[e.first] = seen_id; verts.push_back(e.first); }
63                         if (mark[e.second] != seen_id) { mark[e.second] = seen_id; verts.push_back(e.second); }
64                     }
65                     blocks_edges.push_back(move(edges));
66                     blocks_vertices.push_back(move(verts));
67                 }
68             } else if (disc[v] < disc[u]) {
69                 // Back-edge to ancestor (ensure we only push once per undirected edge)
70                 st.push_back({u, v});
71                 low[u] = min(low[u], disc[v]);
72             }
73         }
74     }
75 
76     void build() {
77         for (int i = 0; i < n; ++i) {
78             if (disc[i] == 0) {
79                 dfs(i);
80                 // Remaining edges on the stack form a final block for this DFS tree
81                 if (!st.empty()) {
82                     vector<pair<int,int>> edges;
83                     while (!st.empty()) { edges.push_back(st.back()); st.pop_back(); }
84                     vector<int> verts;
85                     static vector<int> mark(1, -1);
86                     if ((int)mark.size() < n) mark.assign(n, -1);
87                     int seen_id = i + timer;
88                     for (auto &e : edges) {
89                         if (mark[e.first] != seen_id) { mark[e.first] = seen_id; verts.push_back(e.first); }
90                         if (mark[e.second] != seen_id) { mark[e.second] = seen_id; verts.push_back(e.second); }
91                     }
92                     blocks_edges.push_back(move(edges));
93                     blocks_vertices.push_back(move(verts));
94                 }
95             }
96         }
97     }
98 };
99 
100 int main() {
101     ios::sync_with_stdio(false);
102     cin.tie(nullptr);
103 
104     // Example graph:
105     // Two triangles sharing vertex 2, plus a bridge (2-6)
106     // 0-1-2-0 is a triangle; 2-3-4-2 is another triangle; 2-6 is a bridge
107     int n = 7;
108     BiconnectedComponents bicc(n);
109     auto add = [&](int u,int v){ bicc.addEdge(u,v); };
110     add(0,1); add(1,2); add(2,0); // triangle 0-1-2
111     add(2,3); add(3,4); add(4,2); // triangle 2-3-4
112     add(2,6);                      // bridge 2-6
113     add(4,5); add(5,3);            // add chord 4-5-3 creates extra cycles within second block
114 
115     bicc.build();
116 
117     cout << "Articulation points: ";
118     for (int i = 0; i < n; ++i) if (bicc.isArt[i]) cout << i << ' ';
119     cout << "\n";
120 
121     cout << "Number of blocks: " << bicc.blocks_vertices.size() << "\n";
122     for (size_t id = 0; id < bicc.blocks_vertices.size(); ++id) {
123         cout << "Block " << id << ": vertices {";
124         for (size_t j = 0; j < bicc.blocks_vertices[id].size(); ++j) {
125             if (j) cout << ',';
126             cout << bicc.blocks_vertices[id][j];
127         }
128         cout << "}, edges {";
129         for (size_t j = 0; j < bicc.blocks_edges[id].size(); ++j) {
130             auto e = bicc.blocks_edges[id][j];
131             if (j) cout << ',';
132             cout << '(' << e.first << '-' << e.second << ')';
133         }
134         cout << "}\n";
135     }
136 
137     return 0;
138 }
139

This program implements Tarjan’s edge-stack algorithm to find all biconnected components and articulation points. It maintains discovery times and low-link values, pushes tree and back edges on a stack, and whenever low[v] ≥ disc[u], it pops one component. The result lists each block’s edges and unique vertices and flags all articulation points.

Time: O(n + m)Space: O(n + m)

Building the block-cut tree and answering 2-vertex-connected queries

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Reuse a minimal BCC extractor (edges -> blocks) from the first example
5 struct BCC {
6     int n, timer; vector<vector<int>> g; vector<int> disc, low, parent; vector<bool> isArt; vector<pair<int,int>> st;
7     vector<vector<pair<int,int>>> blocks_edges; vector<vector<int>> blocks_vertices;
8     BCC(int n): n(n), timer(0), g(n), disc(n,0), low(n,0), parent(n,-1), isArt(n,false) {}
9     void addEdge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
10     void dfs(int u){ disc[u]=low[u]=++timer; int child=0; for(int v:g[u]){ if(v==parent[u]) continue; if(!disc[v]){ parent[v]=u; st.push_back({u,v}); ++child; dfs(v); low[u]=min(low[u],low[v]); if(low[v]>=disc[u]){ if(parent[u]!=-1||child>1) isArt[u]=true; vector<pair<int,int>> E; while(true){ auto e=st.back(); st.pop_back(); E.push_back(e); if((e.first==u&&e.second==v)||(e.first==v&&e.second==u)) break; } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=u+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } else if(disc[v]<disc[u]){ st.push_back({u,v}); low[u]=min(low[u],disc[v]); } } }
11     void build(){ for(int i=0;i<n;++i) if(!disc[i]){ dfs(i); if(!st.empty()){ vector<pair<int,int>> E; while(!st.empty()){ E.push_back(st.back()); st.pop_back(); } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=i+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } }
12 };
13 
14 int main(){
15     ios::sync_with_stdio(false);
16     cin.tie(nullptr);
17 
18     int n = 8;
19     BCC bcc(n);
20     auto add=[&](int u,int v){ bcc.addEdge(u,v); };
21     // Build a sample graph with multiple blocks and articulation points
22     add(0,1); add(1,2); add(2,0);        // block A: triangle 0-1-2
23     add(2,3);                            // articulation 2
24     add(3,4); add(4,5); add(5,3);        // block B: triangle 3-4-5
25     add(5,6); add(6,7);                  // path to leaf; edges 5-6 and 6-7 are bridges (single-edge blocks)
26 
27     bcc.build();
28 
29     // Build blocks-per-vertex for fast intersection queries
30     vector<vector<int>> blocksOfVertex(n);
31     for (int id = 0; id < (int)bcc.blocks_vertices.size(); ++id) {
32         for (int v : bcc.blocks_vertices[id]) blocksOfVertex[v].push_back(id);
33     }
34 
35     // Build the block-cut tree: block nodes [0..B-1], articulation nodes [B..B+A-1]
36     int B = (int)bcc.blocks_vertices.size();
37     vector<int> artIndex(n, -1); int A = 0;
38     for (int v = 0; v < n; ++v) if (bcc.isArt[v]) artIndex[v] = A++;
39     int N_bct = B + A; vector<vector<int>> bct(N_bct);
40 
41     for (int bid = 0; bid < B; ++bid) {
42         for (int v : bcc.blocks_vertices[bid]) {
43             if (bcc.isArt[v]) {
44                 int aid = B + artIndex[v];
45                 bct[bid].push_back(aid);
46                 bct[aid].push_back(bid);
47             }
48         }
49     }
50 
51     // Function to answer: are u and v 2-vertex-connected?
52     auto twoVertexConnected = [&](int u, int v){
53         if (u == v) return true; // conventionally true: trivially connected after removing any other single vertex
54         // intersect blocksOfVertex[u] and blocksOfVertex[v]
55         if (blocksOfVertex[u].size() > blocksOfVertex[v].size()) swap(u,v);
56         static int visTime = 1; static vector<int> seen; if ((int)seen.size() < B) seen.assign(B, 0);
57         ++visTime; if (visTime == 0) { fill(seen.begin(), seen.end(), 0); visTime = 1; }
58         for (int id : blocksOfVertex[u]) seen[id] = visTime;
59         for (int id : blocksOfVertex[v]) if (seen[id] == visTime) return true;
60         return false;
61     };
62 
63     // Demo queries
64     vector<pair<int,int>> queries = {{0,2},{0,3},{3,5},{6,7},{4,6}};
65     for (auto [u,v] : queries) {
66         cout << u << " and " << v << (twoVertexConnected(u,v) ? " are " : " are NOT ")
67              << "2-vertex-connected\n";
68     }
69 
70     // Optionally: print the block-cut tree structure (degrees, etc.)
71     cout << "Block-cut tree has " << N_bct << " nodes: " << B << " blocks and " << A << " articulations\n";
72     for (int i = 0; i < N_bct; ++i) {
73         cout << (i < B ? "B":"A") << i - (i < B ? 0 : B) << ":";
74         for (int j : bct[i]) cout << ' ' << (j < B ? 'B' : 'A') << (j < B ? j : j - B);
75         cout << '\n';
76     }
77 
78     return 0;
79 }
80

This program builds the block-cut tree from the extracted blocks: block nodes connect to articulation nodes they contain. It also preprocesses “blocks per vertex” and answers 2-vertex-connected queries by checking if two vertices share any block in O(deg_B(u) + deg_B(v)) time using a timestamped mark array. The block-cut tree is printed to illustrate structure.

Time: O(n + m) preprocessing, O(deg_B(u) + deg_B(v)) per querySpace: O(n + m)

Cycle decomposition inside each biconnected component (cycle basis via DFS)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Minimal BCC extractor from example 1 (trimmed for brevity but complete)
5 struct BCC {
6     int n, timer; vector<vector<int>> g; vector<int> disc, low, parent; vector<bool> isArt; vector<pair<int,int>> st;
7     vector<vector<pair<int,int>>> blocks_edges; vector<vector<int>> blocks_vertices;
8     BCC(int n): n(n), timer(0), g(n), disc(n,0), low(n,0), parent(n,-1), isArt(n,false) {}
9     void addEdge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
10     void dfs(int u){ disc[u]=low[u]=++timer; int child=0; for(int v:g[u]){ if(v==parent[u]) continue; if(!disc[v]){ parent[v]=u; st.push_back({u,v}); ++child; dfs(v); low[u]=min(low[u],low[v]); if(low[v]>=disc[u]){ if(parent[u]!=-1||child>1) isArt[u]=true; vector<pair<int,int>> E; while(true){ auto e=st.back(); st.pop_back(); E.push_back(e); if((e.first==u&&e.second==v)||(e.first==v&&e.second==u)) break; } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=u+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } else if(disc[v]<disc[u]){ st.push_back({u,v}); low[u]=min(low[u],disc[v]); } } }
11     void build(){ for(int i=0;i<n;++i) if(!disc[i]){ dfs(i); if(!st.empty()){ vector<pair<int,int>> E; while(!st.empty()){ E.push_back(st.back()); st.pop_back(); } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=i+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } }
12 };
13 
14 int main(){
15     ios::sync_with_stdio(false);
16     cin.tie(nullptr);
17 
18     // Sample graph with a few cycles
19     int n = 8; BCC bcc(n);
20     auto add=[&](int u,int v){ bcc.addEdge(u,v); };
21     add(0,1); add(1,2); add(2,0);            // triangle (block1)
22     add(2,3); add(3,4); add(4,2);            // triangle (block2)
23     add(3,5); add(5,6); add(6,3);            // triangle (block3)
24     add(6,7);                                 // bridge edge (single-edge block)
25 
26     bcc.build();
27 
28     // For each block, build a local DFS to generate a cycle basis (E - V + 1 cycles for connected blocks)
29     int bid = 0;
30     for (auto &verts : bcc.blocks_vertices) {
31         // Map original vertex ids to local indices [0..k-1]
32         int k = (int)verts.size();
33         unordered_map<int,int> id; id.reserve(k*2);
34         for (int i = 0; i < k; ++i) id[verts[i]] = i;
35         vector<vector<int>> lg(k);
36         int Ecnt = 0;
37         for (auto &e : bcc.blocks_edges[bid]){
38             int a = id[e.first], b = id[e.second];
39             lg[a].push_back(b); lg[b].push_back(a);
40             ++Ecnt;
41         }
42         cout << "Block " << bid << " with V=" << k << ", E=" << Ecnt << "\n";
43         if (k >= 1 && Ecnt >= k) {
44             // DFS to produce cycles on back-edges (ancestor edges). This yields a cycle basis.
45             vector<int> disc(k, 0), par(k, -1), depth(k, 0);
46             int T = 0;
47             vector<vector<int>> cycles;
48 
49             function<void(int)> dfs = [&](int u){
50                 disc[u] = ++T;
51                 for (int v : lg[u]) {
52                     if (v == par[u]) continue;
53                     if (!disc[v]) {
54                         par[v] = u; depth[v] = depth[u] + 1; dfs(v);
55                     } else if (disc[v] < disc[u]) {
56                         // back-edge to ancestor v: form cycle along path u->...->v plus edge (u,v)
57                         vector<int> cyc;
58                         int x = u;
59                         cyc.push_back(verts[u]);
60                         while (depth[x] > depth[v]) {
61                             x = par[x];
62                             cyc.push_back(verts[x]);
63                         }
64                         // close the cycle back to u by printing v then implicit edge (u,v)
65                         cyc.push_back(verts[v]); // include ancestor once; path already includes v at end
66                         // reorder to start at verts[v] if desired; here we keep order from u up to v
67                         cycles.push_back(move(cyc));
68                     }
69                 }
70             };
71 
72             for (int s = 0; s < k; ++s) if (!disc[s]) dfs(s);
73 
74             cout << "  Cycle basis size (expected) = E - V + components = " << (Ecnt - k + 1) << " (if connected)\n";
75             cout << "  Found cycles: " << cycles.size() << "\n";
76             int cid = 0;
77             for (auto &cyc : cycles) {
78                 cout << "    Cycle " << cid++ << ": ";
79                 for (size_t i = 0; i < cyc.size(); ++i) cout << cyc[i] << (i+1==cyc.size()? '\n' : ' ');
80             }
81         } else {
82             cout << "  No cycles (this block is a tree/bridge).\n";
83         }
84         ++bid;
85     }
86 
87     return 0;
88 }
89

For each biconnected component, this program constructs a local graph and runs DFS to record cycles formed by back-edges to ancestors. Each back-edge yields a fundamental cycle, producing a cycle basis whose size matches E - V + 1 for a connected block. Single-edge blocks (bridges) yield no cycles.

Time: O(n + m) to extract blocks, plus O(sum over blocks of (V_b + E_b)) = O(n + m) to build cycle basesSpace: O(n + m)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct BiconnectedComponents {
5	int n, timer;
6	vector<vector<int>> g; // adjacency list (0-indexed)
7	vector<int> disc, low, parent; // discovery time, low-link, parent
8	vector<bool> isArt; // articulation flags
9	vector<pair<int,int>> st; // stack of edges
10
11	// Results: each block as list of edges and list of vertices
12	vector<vector<pair<int,int>>> blocks_edges; // edges in each block
13	vector<vector<int>> blocks_vertices; // unique vertices in each block
14
15	BiconnectedComponents(int n): n(n), timer(0) {
16	g.assign(n, {});
17	disc.assign(n, 0);
18	low.assign(n, 0);
19	parent.assign(n, -1);
20	isArt.assign(n, false);
21	}
22
23	void addEdge(int u, int v) {
24	// undirected simple graph
25	g[u].push_back(v);
26	g[v].push_back(u);
27	}
28
29	void dfs(int u) {
30	disc[u] = low[u] = ++timer;
31	int childCount = 0;
32	for (int v : g[u]) {
33	if (v == parent[u]) continue; // skip the tree edge to parent
34	if (disc[v] == 0) {
35	// Tree edge (u, v)
36	parent[v] = u;
37	st.push_back({u, v});
38	++childCount;
39	dfs(v);
40	low[u] = min(low[u], low[v]);
41
42	// If v's subtree cannot reach an ancestor of u, we found a block
43	if (low[v] >= disc[u]) {
44	if (parent[u] != -1 \|\| childCount > 1) isArt[u] = true;
45
46	vector<pair<int,int>> edges;
47	// Pop until (u, v) is popped
48	while (!st.empty()) {
49	auto e = st.back(); st.pop_back();
50	edges.push_back(e);
51	if ((e.first == u && e.second == v) \|\|
52	(e.first == v && e.second == u)) break;
53	}
54	// Collect unique vertices from these edges
55	vector<int> verts;
56	verts.reserve(edges.size() * 2);
57	// Use a temporary mark array via timestamp to avoid O(log n) set
58	static vector<int> mark(1, -1), seen(1, 0);
59	if ((int)mark.size() < n) { mark.assign(n, -1); seen.assign(n, 0); }
60	int seen_id = u + timer; // any changing id works; uniqueness not required globally
61	for (auto &e : edges) {
62	if (mark[e.first] != seen_id) { mark[e.first] = seen_id; verts.push_back(e.first); }
63	if (mark[e.second] != seen_id) { mark[e.second] = seen_id; verts.push_back(e.second); }
64	}
65	blocks_edges.push_back(move(edges));
66	blocks_vertices.push_back(move(verts));
67	}
68	} else if (disc[v] < disc[u]) {
69	// Back-edge to ancestor (ensure we only push once per undirected edge)
70	st.push_back({u, v});
71	low[u] = min(low[u], disc[v]);
72	}
73	}
74	}
75
76	void build() {
77	for (int i = 0; i < n; ++i) {
78	if (disc[i] == 0) {
79	dfs(i);
80	// Remaining edges on the stack form a final block for this DFS tree
81	if (!st.empty()) {
82	vector<pair<int,int>> edges;
83	while (!st.empty()) { edges.push_back(st.back()); st.pop_back(); }
84	vector<int> verts;
85	static vector<int> mark(1, -1);
86	if ((int)mark.size() < n) mark.assign(n, -1);
87	int seen_id = i + timer;
88	for (auto &e : edges) {
89	if (mark[e.first] != seen_id) { mark[e.first] = seen_id; verts.push_back(e.first); }
90	if (mark[e.second] != seen_id) { mark[e.second] = seen_id; verts.push_back(e.second); }
91	}
92	blocks_edges.push_back(move(edges));
93	blocks_vertices.push_back(move(verts));
94	}
95	}
96	}
97	}
98	};
99
100	int main() {
101	ios::sync_with_stdio(false);
102	cin.tie(nullptr);
103
104	// Example graph:
105	// Two triangles sharing vertex 2, plus a bridge (2-6)
106	// 0-1-2-0 is a triangle; 2-3-4-2 is another triangle; 2-6 is a bridge
107	int n = 7;
108	BiconnectedComponents bicc(n);
109	auto add = [&](int u,int v){ bicc.addEdge(u,v); };
110	add(0,1); add(1,2); add(2,0); // triangle 0-1-2
111	add(2,3); add(3,4); add(4,2); // triangle 2-3-4
112	add(2,6); // bridge 2-6
113	add(4,5); add(5,3); // add chord 4-5-3 creates extra cycles within second block
114
115	bicc.build();
116
117	cout << "Articulation points: ";
118	for (int i = 0; i < n; ++i) if (bicc.isArt[i]) cout << i << ' ';
119	cout << "\n";
120
121	cout << "Number of blocks: " << bicc.blocks_vertices.size() << "\n";
122	for (size_t id = 0; id < bicc.blocks_vertices.size(); ++id) {
123	cout << "Block " << id << ": vertices {";
124	for (size_t j = 0; j < bicc.blocks_vertices[id].size(); ++j) {
125	if (j) cout << ',';
126	cout << bicc.blocks_vertices[id][j];
127	}
128	cout << "}, edges {";
129	for (size_t j = 0; j < bicc.blocks_edges[id].size(); ++j) {
130	auto e = bicc.blocks_edges[id][j];
131	if (j) cout << ',';
132	cout << '(' << e.first << '-' << e.second << ')';
133	}
134	cout << "}\n";
135	}
136
137	return 0;
138	}
139

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Reuse a minimal BCC extractor (edges -> blocks) from the first example
5	struct BCC {
6	int n, timer; vector<vector<int>> g; vector<int> disc, low, parent; vector<bool> isArt; vector<pair<int,int>> st;
7	vector<vector<pair<int,int>>> blocks_edges; vector<vector<int>> blocks_vertices;
8	BCC(int n): n(n), timer(0), g(n), disc(n,0), low(n,0), parent(n,-1), isArt(n,false) {}
9	void addEdge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
10	void dfs(int u){ disc[u]=low[u]=++timer; int child=0; for(int v:g[u]){ if(v==parent[u]) continue; if(!disc[v]){ parent[v]=u; st.push_back({u,v}); ++child; dfs(v); low[u]=min(low[u],low[v]); if(low[v]>=disc[u]){ if(parent[u]!=-1\|\|child>1) isArt[u]=true; vector<pair<int,int>> E; while(true){ auto e=st.back(); st.pop_back(); E.push_back(e); if((e.first==u&&e.second==v)\|\|(e.first==v&&e.second==u)) break; } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=u+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } else if(disc[v]<disc[u]){ st.push_back({u,v}); low[u]=min(low[u],disc[v]); } } }
11	void build(){ for(int i=0;i<n;++i) if(!disc[i]){ dfs(i); if(!st.empty()){ vector<pair<int,int>> E; while(!st.empty()){ E.push_back(st.back()); st.pop_back(); } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=i+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } }
12	};
13
14	int main(){
15	ios::sync_with_stdio(false);
16	cin.tie(nullptr);
17
18	int n = 8;
19	BCC bcc(n);
20	auto add=[&](int u,int v){ bcc.addEdge(u,v); };
21	// Build a sample graph with multiple blocks and articulation points
22	add(0,1); add(1,2); add(2,0); // block A: triangle 0-1-2
23	add(2,3); // articulation 2
24	add(3,4); add(4,5); add(5,3); // block B: triangle 3-4-5
25	add(5,6); add(6,7); // path to leaf; edges 5-6 and 6-7 are bridges (single-edge blocks)
26
27	bcc.build();
28
29	// Build blocks-per-vertex for fast intersection queries
30	vector<vector<int>> blocksOfVertex(n);
31	for (int id = 0; id < (int)bcc.blocks_vertices.size(); ++id) {
32	for (int v : bcc.blocks_vertices[id]) blocksOfVertex[v].push_back(id);
33	}
34
35	// Build the block-cut tree: block nodes [0..B-1], articulation nodes [B..B+A-1]
36	int B = (int)bcc.blocks_vertices.size();
37	vector<int> artIndex(n, -1); int A = 0;
38	for (int v = 0; v < n; ++v) if (bcc.isArt[v]) artIndex[v] = A++;
39	int N_bct = B + A; vector<vector<int>> bct(N_bct);
40
41	for (int bid = 0; bid < B; ++bid) {
42	for (int v : bcc.blocks_vertices[bid]) {
43	if (bcc.isArt[v]) {
44	int aid = B + artIndex[v];
45	bct[bid].push_back(aid);
46	bct[aid].push_back(bid);
47	}
48	}
49	}
50
51	// Function to answer: are u and v 2-vertex-connected?
52	auto twoVertexConnected = [&](int u, int v){
53	if (u == v) return true; // conventionally true: trivially connected after removing any other single vertex
54	// intersect blocksOfVertex[u] and blocksOfVertex[v]
55	if (blocksOfVertex[u].size() > blocksOfVertex[v].size()) swap(u,v);
56	static int visTime = 1; static vector<int> seen; if ((int)seen.size() < B) seen.assign(B, 0);
57	++visTime; if (visTime == 0) { fill(seen.begin(), seen.end(), 0); visTime = 1; }
58	for (int id : blocksOfVertex[u]) seen[id] = visTime;
59	for (int id : blocksOfVertex[v]) if (seen[id] == visTime) return true;
60	return false;
61	};
62
63	// Demo queries
64	vector<pair<int,int>> queries = {{0,2},{0,3},{3,5},{6,7},{4,6}};
65	for (auto [u,v] : queries) {
66	cout << u << " and " << v << (twoVertexConnected(u,v) ? " are " : " are NOT ")
67	<< "2-vertex-connected\n";
68	}
69
70	// Optionally: print the block-cut tree structure (degrees, etc.)
71	cout << "Block-cut tree has " << N_bct << " nodes: " << B << " blocks and " << A << " articulations\n";
72	for (int i = 0; i < N_bct; ++i) {
73	cout << (i < B ? "B":"A") << i - (i < B ? 0 : B) << ":";
74	for (int j : bct[i]) cout << ' ' << (j < B ? 'B' : 'A') << (j < B ? j : j - B);
75	cout << '\n';
76	}
77
78	return 0;
79	}
80

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Minimal BCC extractor from example 1 (trimmed for brevity but complete)
5	struct BCC {
6	int n, timer; vector<vector<int>> g; vector<int> disc, low, parent; vector<bool> isArt; vector<pair<int,int>> st;
7	vector<vector<pair<int,int>>> blocks_edges; vector<vector<int>> blocks_vertices;
8	BCC(int n): n(n), timer(0), g(n), disc(n,0), low(n,0), parent(n,-1), isArt(n,false) {}
9	void addEdge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
10	void dfs(int u){ disc[u]=low[u]=++timer; int child=0; for(int v:g[u]){ if(v==parent[u]) continue; if(!disc[v]){ parent[v]=u; st.push_back({u,v}); ++child; dfs(v); low[u]=min(low[u],low[v]); if(low[v]>=disc[u]){ if(parent[u]!=-1\|\|child>1) isArt[u]=true; vector<pair<int,int>> E; while(true){ auto e=st.back(); st.pop_back(); E.push_back(e); if((e.first==u&&e.second==v)\|\|(e.first==v&&e.second==u)) break; } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=u+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } else if(disc[v]<disc[u]){ st.push_back({u,v}); low[u]=min(low[u],disc[v]); } } }
11	void build(){ for(int i=0;i<n;++i) if(!disc[i]){ dfs(i); if(!st.empty()){ vector<pair<int,int>> E; while(!st.empty()){ E.push_back(st.back()); st.pop_back(); } vector<int> V; static vector<int> mark; if((int)mark.size()<n) mark.assign(n,-1); int id=i+timer; for(auto &e:E){ if(mark[e.first]!=id){ mark[e.first]=id; V.push_back(e.first);} if(mark[e.second]!=id){ mark[e.second]=id; V.push_back(e.second);} } blocks_edges.push_back(move(E)); blocks_vertices.push_back(move(V)); } } }
12	};
13
14	int main(){
15	ios::sync_with_stdio(false);
16	cin.tie(nullptr);
17
18	// Sample graph with a few cycles
19	int n = 8; BCC bcc(n);
20	auto add=[&](int u,int v){ bcc.addEdge(u,v); };
21	add(0,1); add(1,2); add(2,0); // triangle (block1)
22	add(2,3); add(3,4); add(4,2); // triangle (block2)
23	add(3,5); add(5,6); add(6,3); // triangle (block3)
24	add(6,7); // bridge edge (single-edge block)
25
26	bcc.build();
27
28	// For each block, build a local DFS to generate a cycle basis (E - V + 1 cycles for connected blocks)
29	int bid = 0;
30	for (auto &verts : bcc.blocks_vertices) {
31	// Map original vertex ids to local indices [0..k-1]
32	int k = (int)verts.size();
33	unordered_map<int,int> id; id.reserve(k*2);
34	for (int i = 0; i < k; ++i) id[verts[i]] = i;
35	vector<vector<int>> lg(k);
36	int Ecnt = 0;
37	for (auto &e : bcc.blocks_edges[bid]){
38	int a = id[e.first], b = id[e.second];
39	lg[a].push_back(b); lg[b].push_back(a);
40	++Ecnt;
41	}
42	cout << "Block " << bid << " with V=" << k << ", E=" << Ecnt << "\n";
43	if (k >= 1 && Ecnt >= k) {
44	// DFS to produce cycles on back-edges (ancestor edges). This yields a cycle basis.
45	vector<int> disc(k, 0), par(k, -1), depth(k, 0);
46	int T = 0;
47	vector<vector<int>> cycles;
48
49	function<void(int)> dfs = [&](int u){
50	disc[u] = ++T;
51	for (int v : lg[u]) {
52	if (v == par[u]) continue;
53	if (!disc[v]) {
54	par[v] = u; depth[v] = depth[u] + 1; dfs(v);
55	} else if (disc[v] < disc[u]) {
56	// back-edge to ancestor v: form cycle along path u->...->v plus edge (u,v)
57	vector<int> cyc;
58	int x = u;
59	cyc.push_back(verts[u]);
60	while (depth[x] > depth[v]) {
61	x = par[x];
62	cyc.push_back(verts[x]);
63	}
64	// close the cycle back to u by printing v then implicit edge (u,v)
65	cyc.push_back(verts[v]); // include ancestor once; path already includes v at end
66	// reorder to start at verts[v] if desired; here we keep order from u up to v
67	cycles.push_back(move(cyc));
68	}
69	}
70	};
71
72	for (int s = 0; s < k; ++s) if (!disc[s]) dfs(s);
73
74	cout << " Cycle basis size (expected) = E - V + components = " << (Ecnt - k + 1) << " (if connected)\n";
75	cout << " Found cycles: " << cycles.size() << "\n";
76	int cid = 0;
77	for (auto &cyc : cycles) {
78	cout << " Cycle " << cid++ << ": ";
79	for (size_t i = 0; i < cyc.size(); ++i) cout << cyc[i] << (i+1==cyc.size()? '\n' : ' ');
80	}
81	} else {
82	cout << " No cycles (this block is a tree/bridge).\n";
83	}
84	++bid;
85	}
86
87	return 0;
88	}
89