Biconnected components

There are many articles online about graphs and (1-)connected components, but not many about biconnected components (BCCs), even though these are way more interesting and can be used to solve many problems! Especially in competitive programming it is vital to know about this concept.

I will outline what biconnected components are, how they work similar to/different from connected components, and how to find them algorithmically (with C++ code included). Presumed knowledge is knowing what a graph is. Sections:

Biconnectedness in a Problem (introduces runing example)
Edge-Biconnected Components
Tarjan’s Algorithm
C++ Implementation
[Bonus 1: Edge-Disjoint …

Biconnectedness in a Problem (introduces runing example)
Edge-Biconnected Components
Tarjan’s Algorithm
C++ Implementation
Bonus 1: Edge-Disjoint Paths
Bonus 2: Vertex-Biconnected Components
Appendix: List of Relevant Terms
Appendix: Proof of Connection Between Edge-Biconnectedness and Bridges
Appendix: Proof of Connection Between Bridges and Simple Cycles

Biconnectedness in a Problem

Let’s introduce the concept by looking at a problem that BCCs could help solve.

Charlotte is a secret agent for Enforcement of Metro Integrity (EMI), and she is tasked with transporting a top-secret package from one of her informants, Alice, to an undercover agent, Bob. Alice and Bob must not meet each other, because that would ruin the safety of the mission, so they must be at different metro stations, and Charlotte can naturally only use the metro network for transport. The matter is further complicated by the fact that Eve, Charlotte’s adversary, is trying to sabotage the mission by disabling one unknown metro connection! For the sets of meeting locations ( A ) where Alice can meet and ( B ) where Bob can meet, how many possible pairs ( (a, b) ) are there such that Charlotte can safely transport the package from ( a ) to ( b ) no matter which line Eve disables?

Example metro network 1: nodes in the ( A ) set are marked with an A, nodes in the ( B ) set are marked with a B; an example valid pair of locations would be ( (3, 1) ), because no matter which metro line Eve chooses to sabogate, there is still a path from ( 3 ) to ( 1 ).*

The metro network is a graph ( G ) with ( n ) nodes (metro stations) and ( m ) edges (metro lines). ( A ) and ( B ) are then subsets of the set of nodes ( V(G) ). We are trying to find an algorithm with the best possible running time. We can use the following definition to make the objective a bit more precise:

Definition: two nodes ( a, b ) are edge-biconnected if for any edge ( e ), there exists a path from ( a ) to ( b ) that does not go through ( e ).

Then in this problem we are trying to count the number of pairs ( (a, b) ) with ( a \in A ) and ( b \in B ) that are edge-biconnected. After all, no matter what edge Eve sabotages, we always still have a path between the two nodes.

The most naive algorithm would be to consider each ( a \in A ) and ( b \in B ). We would then go over each edge, remove it, and check if there is still a path from ( a ) to ( b ) using a simple graph traversal. This approach would have a time complexity of ( O(|A| \cdot |B| \cdot m \cdot (n + m)) ), which is very bad.

We could try to speed up this approach by precomputing for each edge the connected components (CCs) of the graph without that edge, making the path checking constant time. First we would start with the set of all ( (a, b) ) pairs, and iteratively remove pairs that we find can be blocked off by Eve’s sabotage. Then we would iterate over each of the ( m ) edges, and: (1) remove it and compute for each node in which connected component it lies (( O(m + n) ) time using a simple graph traversal), and (2) for each ( (a, b) ) pair, remove it if they do not both lie in the same connected component (now a constant time operation, so ( O(|A| \cdot |B|) ) overall). This leads to to a complexity of ( O(m \cdot ((n + m) + |A| \cdot |B|)) ), which is definitely an improvement, and we considered how to leverage connected components. Click through the animation below to see how this algorithm would work (the dashed circles indicate connected components with the edge removed). However, the running time is still quite miserable.

If Eve sabotages this edge: all nodes can reach all nodes.

If Eve sabotages this edge: remove pairs starting with 5 ending with 1/6/7.

If Eve sabotages this edge: all nodes can reach all nodes.

If Eve sabotages this edge: remove pairs starting with 2/4/5 ending with 6/7, and pairs starting with 6/8 ending with 1/5.*

If Eve sabotages this edge: all nodes can reach all nodes.

The final set of pairs is ( { (2, 1), (4, 1), ~~ (5, 5), ~~ (6, 6), (6, 7), (8, 6), (8, 7) } ).

In this example, we are definitely doing a lot of unnecessary work, and you might also notice that the final set of pairs has a specific pattern to it (whitespace to make this a bit more obvious). We can (suggestively) draw the pairs in the graph as follows:

Notice that we just have a few clusters of nodes, and within each cluster every possible pair is interconnected (a clustering like this is called a partition of the nodes). Can we prove that we can always find such a clustering/partition? Or could it be that in some graph, there is an edge-biconnected pair ( x, y ), an edge-biconnected pair ( y, z ), but not an edge-biconnected pair ( x, z )? (Think about counterexamples, or convince yourself this should always hold.)

Edge-Biconnected Components

Okay, I am kind of giving it away by naming this section like this. But it is a very doable exercise to prove that such a partition is always possible, where within each cluster all the pairs are connected through a pair of edge-disjoint paths, and between two distinct clusters, there are no pairs connected in that way. When thinking about partitions, you should always think about the mathematical concept of an equivalence relation. If edge-biconnectedness were an equivalence relation, we would need to prove the following three properties:

Reflexivity: any node ( u ) is edge-biconnected to itself.
Symmetry: if ( u ) is edge-biconnected to ( v ), then ( v ) must be edge-biconnected to ( u ).
Transitivity: if ( u ) is edge-biconnected to ( v ) and ( v ) is edge-biconnected to ( w ), then ( u ) must be edge-biconnected to ( w ). It turns out that edge-biconnectedness is in fact an equivalence relation. The proofs for these properties are definitely doable to do for yourself! (Try this! Or look at the proof for the first property and then try the other two yourself. For transitivity, you have to consider that the two assumed paths can be overlapping.) Regardless, I will give the proof here, together with a “proof by picture”:
Reflexivity: let ( u ) be any node. Obviously no matter what edge we remove, we still have a path from ( u ) going to itself, namely the empty path. Therefore, ( u ) is edge-biconnected to ( u ).
Symmetry: let ( u ) and ( v ) be any nodes, assume that ( u ) is edge-biconnected to ( v ), and let ( e ) be any edge that we must not use. Because ( u ) was edge-biconnected to ( v ), we can choose ( p ) to be the path from ( u ) to ( v ) that does not use ( e ). Because this path lives in an undirected graph, we can reverse the path to get a path from ( v ) to ( u ) that still does not use ( e ). Therefore, ( v ) is edge-biconnected to ( u ).
Transitivity: let ( u ), ( v ) and ( w ) be any nodes, assume that ( u ) is edge-biconnected to ( v ) and that ( v ) is edge-biconnected to ( w ), and let ( e ) be any edge that we must not use. Because ( u ) was edge-biconnected to ( v ), we can choose ( p ) to be the path from ( u ) to ( v ) that does not use ( e ). Because ( v ) was edge-biconnected to ( w ), we can choose ( q ) to be the path from ( v ) to ( w ). If ( p ) and ( q ) do not overlap in any edges, simply concatenate to get a path ( p q ) from ( u ) to ( w ). If they do however overlap at some point, take the subpath ( p’ ) of ( p ) from ( u ) to the earliest point where the overlap, take the subpath ( q’ ) of ( q ) from that point to ( w ), and concatenate to get a path ( p’ q’ ) from ( u ) to ( w ) that does not use ( e ) and does not overlap with itself. Therefore in either case, ( v ) is edge-biconnected to ( w ). (See figure.)

Example for transitivity proof: ( e ) marks the sabotaged edge.

Example for transitivity proof: path from ( u ) to ( v ).

Example for transitivity proof: path from ( v ) to ( w ).

Example for transitivity proof: red marks the first overlapping node of the two paths.

Example for transitivity proof: concatenated path from ( u ) to ( w ).

This gives us a new algorithm for our problem. First compute the edge-biconnected components for the entire graph. Then within each component count how many ( A ) nodes and how many ( B ) nodes there are. Because within a component each pair of nodes is edge-biconnected, we can simply multiply the A count by the B count and add this value to the result. Between any two different components there are no edge-biconnected pairs, we are not missing any pairs. Now all we need is an algorithm for computing edge-biconnected components!

Tarjan’s Algorithm

As could be seen in the example of our connected-component-based algorithm, there are certain edges that, when removed, will split up the graph into more connected components. These edges are called bridges.

Definition: an edge ( { u, v } ) is a bridge if there is no path between ( u ) and ( v ) in ( G - { u, v } ).

If we can find the bridges of the graph, then finding the edge-biconnected components will be very easy, because they are simply the connected components of the graph with all bridges removed. This follows from the following lemma.

Lemma 1: two nodes are edge-biconnected if and only if they are in the same connected component of the graph with all bridges removed. (See the appendix for the proof, which is safe to skip.)

The algorithm for finding bridges was invented by famous computer scientist Robert Tarjan and only uses depth-first search. (Fun fact: Tarjan’s brother James is a chess grandmaster.) Let’s look at the first observation that makes this algorithm works:

Lemma 2: an edge ( e ) is a bridge if and only if there does not exist a simple cycle that goes through ( e ). (See the appendix for the proof, which is safe to skip.)

We can check this condition for all edges by performing a DFS and looking at the back-edges of the DFS tree. For instance, this is what a DFS tree looks like for the example if we start at node 1:

A possible DFS tree. Filled arrows are tree-edges and dotted arrows are back-edges.

We know that back edges are always part of a cycle. Thus, we can make the following two observations about the connection between bridges, by using lemma 2.

Observation: a back edge is never a bridge.

Observation: a tree edge ( (u, v) ) is a bridge if and only if none of the descendants of ( v ) has a back edge to an ancestor of ( u ).

Tarjan’s algorithm maintains for every node a ( \mathit{low} ) value, which is the minimum between (1) the DFS entry time of the node itself, (2) the entry times of all back-edge neighbors, and (3) the ( \mathit{low} ) values of the children. Then a tree edge ( (u, v) ) is a bridge if and only if ( low[v] ) is strictly greater than the entry time of ( u ). Essentially, this means that when the algorithm visits a back edge ( (u, v) ), all of the tree edges between ( v ) and ( u ) are marked as not being a bridge as soon as we go back up the DFS tree.

Step through the example below. I have made the graph such that the DFS entry time matches the node labels.

All nodes start with ( \mathit{low} ) equal to the DFS entry time.

Visit tree edge ( (1, 2) ).

Visit tree edge ( (2, 3) ).

Visit back edge ( (3, 1) ): update ( \mathit{low}[3] := \min(\mathit{low}[3], 1) ). All tree edges shown in red thus cannot be bridges.*

Visit tree edge ( (3, 4) ).

Visit back edge ( (4, 1) ): update ( \mathit{low}[4] := \min(\mathit{low}[4], 1) ). All tree edges shown in red thus cannot be bridges.*

Visit tree edge ( (4, 5) ).

Node 5 has no children, so ( \mathit{low}[5] = 5 ). Since ( \mathit{low}[5] > 4 ), the edge is a bridge.*

Visit tree edge ( (4, 6) ).

Visit tree edge ( (6, 7) ).

Visit tree edge ( (7, 8) ).

Visit back edge ( (8, 6) ): update ( \mathit{low}[8] := \min(\mathit{low}[8], 6) ). All tree edges shown in red thus cannot be bridges.*

So ( \mathit{low}[8] = 6 ).

Update ( \mathit{low}[7] := \min(\mathit{low}[7], \mathit{low}[8]) ).

Update ( \mathit{low}[6] := \min(\mathit{low}[6], \mathit{low}[7]) ). Since ( \mathit{low}[6] > 4 ), the edge is a bridge.*

Update ( \mathit{low}[4] := \min(\mathit{low}[4], \mathit{low}[6]) ).

Update ( \mathit{low}[3] := \min(\mathit{low}[3], \mathit{low}[4]) ).

Update ( \mathit{low}[2] := \min(\mathit{low}[2], \mathit{low}[3]) ).

Update ( \mathit{low}[1] := \min(\mathit{low}[1], \mathit{low}[2]) ).

As you can see, the algorithm finds the bridges, and even appears to identify edge-biconnected components. It can be modified to find the edge-biconnected components and even articulation points (which is a concept related to vertex-biconnectedness) in a single pass, but understanding and proving why this works is quite difficult.

Since the algorithm only performs a DFS and maintains some integers associated with the nodes, it has a time complexity of ( O(|V| + |E|) ) and a space complexity of ( O(|V|) ) (assuming the graph space usage itself is not counted).

C++ Implementation

Now we can solve the original metro problem. The full code is available on this website. I also have code that computes the edge-biconnected components without the metro stuff and that also works for non-simple graphs (with self loops or multi-edges), which I tested on judge.yosupo.jp. All code is licensed under GPL3 (see the COPYING file).

First we set up the graph data structure and implement the bridge-finding algorithm. The nodes keep track of the ( \mathit{low} ) value and whether they are in the A and/or B set. Tarjan’s algorithm performs a standard DFS and computes the ( \mathit{low} ) value for each node, and puts an edge in the bridges set if it meets the condition given in the previous section.

// Copyright 2025 emilia-h
#include <iostream>
#include <set>
#include <utility>
#include <vector>

struct Node {
std::vector<int> adj;
bool visited = false;
int dfsEntryTime = -1;
int low = -1;
bool isA = false, isB = false;
};

void dfs(
std::vector<Node>& graph,
int i, int parent,
int& time, std::set<std::pair<int, int>>& bridges
) {
graph[i].dfsEntryTime = time++;

int low = graph[i].dfsEntryTime;
for (int j : graph[i].adj) {
if (j == parent) { // edge back to parent
continue;
} else if (graph[j].visited) { // back edge
low = std::min(low, graph[j].dfsEntryTime);
} else { // tree edge
graph[j].visited = true;
dfs(graph, j, i, time, bridges);
low = std::min(low, graph[j].low);

if (graph[j].low > graph[i].dfsEntryTime) {
bridges.insert({i, j});
bridges.insert({j, i});
}
}
}
graph[i].low = low;
}

std::set<std::pair<int, int>> getBridges(std::vector<Node>& graph) {
std::set<std::pair<int, int>> bridges;
int time = 0;
for (int i = 0; i < graph.size(); i++) {
if (graph[i].visited) continue;
graph[i].visited = true;
dfs(graph, i, -1, time, bridges);
}
return bridges;
}

Then we have another DFS procedure which, given a node ( i ), computes the number of A nodes and B nodes within the edge-biconnected component that it lies in. It does this by never passing through bridges, meaning it will not go to another edge-biconnected component.

std::pair<int, int> countAB(
std::vector<Node>& graph,
int i,
const std::set<std::pair<int, int>>& bridges
) {
if (graph[i].visited) return {0, 0};
graph[i].visited = true;
std::pair<int, int> result {0, 0};
if (graph[i].isA) result.first++;
if (graph[i].isB) result.second++;
for (int j : graph[i].adj) {
// don't traverse bridges (act like they are removed from the graph)
if (bridges.count({i, j})) continue;
auto abCount = countAB(graph, j, bridges);
result.first += abCount.first;
result.second += abCount.second;
}
return result;
}

Finally, we have some code that reads the graph and the set of A and B nodes. It runs the two DFS passes above for the whole graph. For each edge-biconnected component, it adds the product of the number of A nodes and B nodes, because that is how many ( (a, b ) ) pairs you can find within an edge-biconnected component that Eve cannot sabotage.

int main() {
int n, m, a, b;
std::cin >> n >> m >> a >> b;

std::vector<Node> graph(n);
for (int i = 0; i < m; i++) {
int v, w;
std::cin >> v >> w;
graph[v - 1].adj.push_back(w - 1);
graph[w - 1].adj.push_back(v - 1);
}
for (int i = 0; i < a; i++) {
int v;
std::cin >> v;
graph[v - 1].isA = true;
}
for (int i = 0; i < b; i++) {
int v;
std::cin >> v;
graph[v - 1].isB = true;
}

auto bridges = getBridges(graph);

for (auto& node : graph) node.visited = false;

// go over each edge-biconnected component and count A and B nodes
int result = 0;
for (int i = 0; i < n; i++) {
if (graph[i].visited) continue;
auto abCount = countAB(graph, i, bridges);
result += abCount.first * abCount.second;
}
std::cout << result << "\n";

return 0;
}

The input format is as follows. The first line is ( n, m, a, b ), which are the number of nodes, the number of edges, the number of A nodes, and the number of B nodes respectively. Then follow ( m ) lines of pairs ( v~w ), which are the edges. It is assumed that the graph is simple. Then follow ( a ) lines of integers, which are the A nodes, and then ( b ) lines of integers, which are the B nodes. All nodes in the input are 1-based. There is an example input available that encodes the graph we’ve been using as an example, for which the code gives the correct answer 7.

Bonus 1: Edge-Disjoint Paths

Another way to state the edge-biconnectedness property is that there exist two edge-disjoint paths from ( a ) to ( b ), i.e., paths that do not have any of the same edges. For instance, in the example there are two edge-disjoint paths from node 2 to 1: one that goes from 2 directly to 1, and one that goes from 2 through 3 to 1. However, there are no two edge-disjoint paths from node 5 to 7: any path must go through the same edge ( { 4, 6 } ), so we cannot choose two paths to be fully edge-disjoint. The proof that this is a property that holds if and only if the nodes are edge-biconnected is not trivial. You can see the picture for an example that we have two edge-disjoint paths for each edge-biconnected pair, but not for any other pairs:

Pair: ( (2, 1) )

Pair: ( (4, 1) )

Pair: ( (5, 5) )

Pair: ( (6, 6) )

Pair: ( (6, 7) )

Pair: ( (8, 6) )

Pair: ( (8, 7) )

Also note that in an undirected graph, we can see two edge-disjoint paths from ( a ) to ( b ) as an edge walk that goes from ( a ) to ( b ) and then back to ( a ) again, without repeating any edges. This is kind of like a cycle going through ( a ) and ( b ), except we may go over the same node several times.

Bonus 2: Vertex-Biconnected Components

We can repeat the problem that we stated before but change one thing: what if after you pick a station for Alice and one for Bob, Eve sabotages a metro station instead of a metro line? (She would not be able to sabotage the metro station that Alice or Bob was in.) Do we still have an equivalence relation on the nodes like with edge-biconnectedness? I will not discuss it in this article, but consider the following example and think about if the transitivity property holds for vertex-biconnectedness:

I will also leave you with a hint: a node can be part of multiple vertex-biconnected components. Consider instead an equivalence relation on the edges (it’s a cute little symmetry that edge-biconnectedness gives an equivalence relation on the vertices, and vertex-biconnectedness gives an equivalence relation on the edges).

Appendix: List of Relevant Terms

Here is a list of terms used in the theory for edge-biconnectedness and vertex-biconnectedness:

Edge-biconnectedness (for pairs of nodes): a node ( u ) is edge-biconnected to a node ( v ) if for any edge ( e ), we can find a path from ( u ) to ( v ) that does not go through ( e ).
Edge-biconnectedness (for whole undirected graphs): a graph is edge-biconnected if the graph is connected even if any one edge is removed.
Edge-biconnected components: a subset of nodes forms an edge-biconnected component if each pair of nodes within it is edge-biconnected, and it cannot have any additional nodes added to it and still have this property. (The edge-biconnected components of any graph are the equivalence classes of the edge-biconnectedness equivalence relation.)
Bridge: an edge is a bridge if, when removed, the number of connected components is increased (in the example graph there are two such edges, which you can see by stepping through the second figure).
Vertex-biconnectedness (for pairs of nodes): a node ( u ) is vertex-biconnected to a node ( v ) if there exist two vertex-disjoint paths from ( u ) to ( v ), or ( u = v ). (Note that this is not an equivalence relation.)
Vertex-biconnectedness (for whole undirected graphs): a graph is vertex-biconnected if the graph is connected even if any one node is removed.
Vertex-biconnected component: a subset of nodes forms a vertex-biconnected component if each pair of nodes within it is vertex-biconnected, and it cannot have any additional nodes added to it and still have this property. (Note that the vertex-biconnected components of a graph are not necessarily a partition of the nodes.)
Articulation point: a node is an articulation point if it is part of more than one vertex-biconnected component.

Appendix: Proof of Connection Between Edge-Biconnectedness and Bridges

Lemma 1: for any undirected graph ( G ), for any two nodes ( u, v \in V(G) ), ( u ) and ( v ) are edge-biconnected if and only if ( u ) and ( v ) are in the same connected component of ( G ) with all bridges removed.

Proof. For convenience, define ( G’ ) to be ( G ) with all bridges removed.

( (\Rightarrow) ) Assume ( u ) and ( v ) are edge-biconnected. For a contradiction, suppose ( u ) and ( v ) are not in the same connected component of ( G’ ), i.e., all paths from ( u ) to ( v ) go through some bridge in ( G ). Since edge-biconnectedness implies connectedness, there must exist at least one path ( p ) between them in ( G ), and choose ( e ) to be a bridge that this path goes through. From edge-biconnectedness, we can instead choose a path ( q ) that does not go through ( e ). Choose ( C ) to be the first connected component of ( G’ ) that ( q ) passes through and that ( p ) also goes through, and that is not just the connected component that ( u ) lies in (we know such a connected component must exist, because ( p ) and ( q ) at least meet in the component of ( v ) in ( G’ ), and that component is separate from the component of ( u ) because we passed through the bridge ( e )). We can join up these paths ( p ) and ( q ) in that connected component through edges that are not bridges. Now we have a cycle passing through a bridge, which is a contradiction because it implies that both endpoints of the bridge are in the same connected component even if ( e ) was removed (see also lemma 2).
( (\Leftarrow) ) Assume ( u ) and ( v ) are in the same connected component of ( G’ ). To prove their edge-biconnectedness, let ( e ) be any edge. If ( e ) is a bridge or lies outside of the connected component of ( u ) and ( v ), then trivially there exists a path from ( u ) to ( v ) that does not use ( e ). Otherwise, ( e ) must not be a bridge and that means that removing it from ( G ) does not change what vertices are connected to each other, i.e., ( u ) and ( v ) would still lie in the same connected component in ( G - e ). This means there exists a path from ( u ) to ( v ) in ( G - e ) and thus there exists a path in ( G ) that does not use ( e ) going from ( u ) to ( v ). Either way, we have a path from ( u ) to ( v ), proving that ( u ) is edge-biconnected to ( v ).

Appendix: Proof of Connection Between Bridges and Simple Cycles

Lemma 2: an edge ( { u, v } ) is a bridge if and only if all simple cycles do not go through ( { u, v } ).

Proof. For convenience, define ( G’ := G - { u, v } ) to be the graph with the edge removed.

( (\Rightarrow) ) Let ( { u, v } ) be a bridge and let ( c ) be a simple cycle in ( G ), and assume for a contradiction that ( c ) goes through ( { u, v } ). Then we can remove the edge ( { u, v } ) from the cycle and still have a path between ( u ) and ( v ) in ( G’ ). This directly contradicts the assumption that ( { u, v } ) was a bridge.
( (\Leftarrow) ) Let ( { u, v } ) be an edge through which all simple cycles do not pass. For a contradiction, suppose that ( { u, v } ) was not a bridge and thus ( u ) and ( v ) are still connected in ( G’ ) and thus there exists a path ( { v, v_1 }, ..., { v_n, u } ) in ( G’ ). Since ( { u, v } ) is an edge in ( G ), we can connect the two ends of the path and get a simple cycle in ( G ) that passes through ( { u, v } ). This contradicts the assumption. Copyright emilia-h 2025 licensed under CC BY-SA 4.0

Similar Posts