OpenSource Internship opportunity by OpenGenus for programmers. Apply now.
Turns out, biconnected components are one of the most important topic in design analysis of algorithms, data structures and in many competitive exams.
Biconnected components are defined as a maximal biconnected subgraph.
Lets understand it better!
Table Of Contents
 Prerequisites
1.1 Graph
1.2 Articulation Point
1.3 Biconnected Graph  What Are Biconnected Components
 How To Build A Biconnected Graph
 Identify Articulation Point In A Graph
 Identify Biconnected Components In A Graph
 Why These Are Important
1 Prerequisites
These are some of the things which you should know before we get to our main topic!
1.1 Graph
Graphs can be defined as a mathematical structure which represents a specific function. It is constructed by connecting a set of points using lines. Each points are known as vertex (node) and the line joining it is known as edges. In the below graph A,B,C,D and E are known as vertex and the lines joining them are known as edges.
These graphs have a lot of applications in a lot of different fields like computer science, physics, chemistry etc. There is even a study called graph theory to learn about the relationship between nodes and edges.
So its a very important concept. The topic biconnected component is a part of this theory. There are a lot of different types of graphs, eg: Conected graph: If in a graph there is a path between every pair of distinct vertices we can call it a connected graph.1.2 Articulation Point
A vertex V in a connected graph G is an articulation point (cut point) if the deletion of vertex V along with all edges incident to V disconnects the graph into two or more nonempty components.
Lets demonstrate it with an example:
Fig 1.2 shows a connected graph
Here we can say vertex 2 is an articulation point, because if we remove the vertex 2 along with the incident edges we can observe that the graph splits into two nonempty component.
After deleting vertex 2 and the incident edges of vertex 2, the given graph is divided into two nonempty components as in the figure above.
=> vertex 2 is an articulation point
1.3 Biconnected Graph
We can call a graph G a biconnected graph if it contains zero articulation point.
Example:
2. What Are Biconnected Components
A maximal biconnected subgraph is a Biconnected component. Its really simple if you understand the sentance carefully.
Take a biconnected subgraph of a graph, then keep on adding the neighbouring vertices and edges and take a step back if you find an articulation point. So now you will have a biconnected subgraph of the given graph with maximum nodes possible such that there are no articulation point.
In simple words a biconnected component is a part of a graph that is connected in a special way. Imagine you have a graph with nodes (called vertices) and lines (called edges)
connecting them. A biconnected component is a group of vertices and edges that are all connected to each other in a way that you can always get from one vertex to another using two
different paths.
Note: You might have to read it a couple of times to get the whole idea.
Note From the defenition you might have understood that any biconnected graph can be a biconnected component, as any graph is a subgraph of itself.
Lets take an example:
Here the given graph has 3 articulation points ie, vertex 2, 3, 5, as the graph splits into various parts if we remove one vertex and the edges incident to it.
So the following are the biconnected components in the graph. As you might observe if we take two of them togeher they will have atmost 1 vertex in common and that vertex is none other than the articulation point. Take any pair and check.
3. How To Build A Biconnected Graph
Steps to follow to build a biconnected graph:
 Check whether the given graph is biconnected or not.
 If its not biconnected identify all the articulation point.
 After obtaining the articulation points, determine the set of edges whose inclusion makes the graph connected in the absence of articulation point.
Now lets look the steps for our graph (Fig 2).
 The given grapg G is not a biconnected graph, the articulation points are 2,3 and 5.
 To transform G to biconnected graph new edges are included to te articulation point.
 Edges corresponding to the articulation point 2 are (1,5) and (3,8).
 Edges corresponding to the articulation point 3 are (4,10) and (2,9).
 Edges corresponding to the articulation point 5 are (6,7).
So lets add these edges.
The edges added are represented as dotted lines.
After the edition of these lines we can observe that it is a biconnected graph.
4. Identify Articulation Point In A Graph
An articulation point (or cut vertex) in a graph is a vertex that, when removed, increases the number of connected components in the graph. In other words, an articulation point is a vertex that "separates" the graph into two or more separate parts, and if it is removed, those parts will become disconnected.
One of the simplest algorithms for identifying articulation points in a given graph is to perform a depthfirst search (DFS) traversal of the graph and keep track of the following information for each vertex:
 The DFS number of the vertex: This is the order in which the vertex was visited during the DFS traversal.
 The lowlink value of the vertex: This is the minimum DFS number of any vertex that can be reached from the current vertex by following zero or more DFS tree edges and then at least one back edge.
To identify the articulation points in the graph, we can use the following steps:
 Start by setting the DFS number and lowlink value of each vertex to be the same.
 For each vertex, do the following:
a. Consider all of the vertices that are reachable from the current vertex by a single edge.
b. For each of these vertices, compute the lowlink value using the following rule: If the lowlink value of the current vertex is greater than the lowlink value of the reachable vertex, set the lowlink value of the current vertex to be the same as the lowlink value of the reachable vertex.
 If the lowlink value of the current vertex is equal to its DFS number, then it is an articulation point.
 Repeat this process for all vertices in the graph.
This algorithm has a time complexity of O(V+E), where V is the number of vertices and E is the number of edges in the graph. This is because the algorithm performs a depthfirst search (DFS) traversal of the graph, which has a time complexity of O(V+E). The space complexity of the algorithm is also O(V+E), as it stores the DFS number and lowlink value for each vertex in the graph.
The algorithm described above will work for any type of graph, including directed and undirected graphs, as well as graphs with selfloops and multiple edges.
5. Identify Biconnected Components
Let's look at how to find a biconnected component in a graph. For this we will use Tarjan's algorithm for finding biconnected components in a graph. It was developed by Robert Tarjan in 1972.
Algorithmic steps:

Initialize a counter
dfn
to 1, which will be used to assign a depthfirst search (DFS) number to each vertex. Initialize an empty stackS
and a list of biconnected componentscomponents
. 
Run a DFS on the graph, keeping track of the following information for each vertex
v
:dfn[v]
: the DFS number ofv
low[v]
: the lowest DFS number reachable fromv
parent[v]
: the parent ofv
in the DFS tree

For each vertex
v
visited in the DFS, do the following: If
v
is the root of the DFS tree, and it has more than one child, add all of its children to the current biconnected componentC
.  If
v
is not the root of the DFS tree, andlow[v] >= dfn[v]
, thenv
is an articulation point. In this case, addv
and all vertices on the stackS
that have a DFS number greater thanlow[v]
to the current biconnected componentC
.
 If

For each edge
(u, v)
in the graph, do the following: If
dfn[u] < low[v]
, then(u, v)
is a back edge. In this case, setlow[v] = dfn[u]
.  If
dfn[u] > dfn[v]
, then(u, v)
is a forward edge. In this case, pushv
onto the stackS
.
 If

When the DFS is complete, the list of biconnected components components will contain all of the biconnected
components
of the graph.
Lets look at the C++ imlementation of this:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 1e5 + 5;
int n, m;
vector<int> adj[N];
int dfn[N], low[N], parent[N], timeStamp;
stack<int> S;
vector<vector<int>> components;
void dfs(int u) {
dfn[u] = low[u] = ++timeStamp;
S.push(u);
for (int v : adj[u]) {
if (dfn[v] == 0) {
parent[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
vector<int> component;
int w;
do {
w = S.top();
S.pop();
component.push_back(w);
} while (w != v);
component.push_back(u);
components.push_back(component);
}
} else if (v != parent[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) {
dfs(i);
}
}
for (const auto& component : components) {
for (int v : component) {
cout << v << " ";
}
cout << endl;
}
return 0;
}
This code first reads in the number of vertices n
and edges m
in the graph, and then reads in the edges of the graph. It then runs a DFS on the graph and uses the stack S
and the arrays dfn
, low
, and parent
to identify the biconnected components of the graph. Finally, it prints out the vertices in each biconnected component.
Here is an example of input and output for this code:
Input:
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
Output:
1 3 2
4 6 5
This input represents a graph with 6 vertices and 7 edges, with biconnected components consisting of the vertices 1, 2, 3 and 4, 5, 6. The output correctly lists these biconnected components.
The time complexity of Tarjan's algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. The space complexity is also O(V + E), as the algorithm uses an adjacency list to represent the graph and a stack to store the vertices on the current DFS path.
6. Why These Are Important?
There are many applications of these in many fields.
An articulation point (or cut vertex) in a graph is a vertex that, when removed along with all the edges incident to it, increases the number of connected components in the graph. In other words, an articulation point is a vertex that plays a key role in keeping the graph connected.
Biconnected components, on the other hand, are subgraphs of a graph that are themselves connected and do not have any articulation points.
These concepts are important because they can be used to analyze the connectivity and structural properties of a graph. For example, an articulation point can be used to identify the most critical vertices in a network, such as bridges in a road network or routers in a computer network. Biconnected components can be used to identify the most robust parts of a graph, as they remain connected even if one of their vertices is removed.
In addition, algorithms for finding articulation points and biconnected components are important building blocks for other graph algorithms, such as finding bridges and cycles in a graph, and for analyzing the structure of graphs in general.
By the end of this article at OpenGenus, you must have complete knowledge on biconnected components, lets test your knowledge with a question!