A `bioconnected component`

of a graph is a connected subgraph that **cannot be** broken into disconnected pieces by deleting any single node (and its incident links). An **articulation point** is a node of a graph whose removal would cause an increase in the number of connected components.

## Scope

- This article does not discuss the syntax of writing code in
**C++ language**. Although this article discusses the articulation point, the program to find articulation points in a graph is out of the scope of this article. `Big-O`

notation is used to define the time complexity of the algorithms discussed in this article.- Basic knowledge of
**graph data structure**,**depth-first search(DFS)**technique,**articulation points**in the graph and how to calculate the**time complexity of recursive programs**is expected to fully understand this article.

**Before diving into `Biconnected components`

let’s first understand what is a **Biconnected Graph** and how to check whether a graph is Biconnected or not.**

## Takeaways

Complexities of the nim’s game:

`Time Complexity`

:$O(V + E)$`Space Complexity`

:$O(V)$

‘v’: No of nodes

‘E’: No of edges

## Biconnected Graph

A graph is a `Biconnected graph`

if:

- There is a path from any node to any other node, i.e.
*the graph must be connected*. - After removing any node and all the associated edges from the graph,
*it still remains connected*, i.e. there is always a path between any two nodes even after removing any node from the graph. - For example consider the graphs below,

You can try and remove every possible node from any graph, it always remains connected. And also all of the graphs are one single component, there is a path from any node to any other node.

- Consider the graph shown below, it is not a
`Biconnected graph`

because if we remove the node with`value 2`

, it increases the number of connected components and there is no edge between`node 1`

and`node 5`

, or`node 4`

and`node 6`

etc.

- A node whose removal from the graph increases the number of connected components is called an
**Articulation Point**. In the above graph, the node with`value 2`

*is an articulation point*. - A graph can contain multiple articulation points. We will also discuss the algorithm to detect the articulation points in a graph.
- To check whether a graph is
`Biconnected`

or not, we mainly need to check two things in a graph,*The graph is connected*, i.e. there must be a path between any two nodes in the graph.*There is no articulation point in graph*, as discussed above that a`Biconnected graph`

has no articulation points.

## Algorithm to Detect Articulation Point in a Graph

The algorithm to detect the `articulation point`

in a graph is purely based on `depth-first-search(DFS)`

which is a common traversal algorithm in graph data structure. *Let’s discuss some terminologies that we will be using to detect the articulation point,*

**Discovery Time**(`disc[node]`

): It is the time when a particular node is visited in a`DFS`

call. It always starts with`1`

(*for the sake of implementation, since all we care about is which node is discovered when*) and is incremented by`1`

as we visit a new node in the`DFS`

call.- To record the discovery time of each node in the graph we will be using an array
`disc[]`

of size equal to the number of nodes in the graph. - In the graph below, we assign discovery time to each node if a
`DFS`

call is made to source`node 1`

. The`DFS`

tree explains the order in which the nodes are visited in`DFS`

call.

- To record the discovery time of each node in the graph we will be using an array

**Parent Array**(`par[node]`

): We will also maintain a parent array to keep track of the parent of each node.`Parent[i]`

for a`node i`

determines from which node did the DFS call has been made to`node i`

. Source node has**parent = -1**.- In the below graph value written to the side of the node are the parent values of that node.
`Node 2`

has a parent value equal to`1`

, which is indeed the node that made the DFS call to`node 2`

.`Node 2`

then made DFS call to`node 5`

and`node 3`

, that’s why their parent values are`2`

.

**Lowest Reachable Ancestor**(`low[node]`

): The low value of a node is the lowest possible discovery time of a previously discovered node if we ignore the current`DFS`

path.

- Consider the above graph, if the source node is
`1`

then,`Low[1] = 1`

*because it is the first node to be discovered in*`DFS`

call,`Low[2] = 2`

*because there is no other path leading to any other previously discovered node except the current path*.,`Low[3] = 3`

*because there is no other path leading to any other previously discovered node except the current path*.,`Low[4] = 1`

*because there is a path from node*`4`

to node`1`

, which is not the current DFS path and is leading to a previously discovered node.,`Low[5] = 5`

*because there is no other path leading to any other previously discovered node except the current path*.

## Algorithm to find the Articulation Point

- Take a source node and make a DFS call, assign both the
`low[]`

value and`disc[]`

time equal to time, as`disc[]`

will not change but`low[]`

value might change when we backtrack from a node in DFS call. In graph there are multiple paths to visit the same node and it might affect the discovery time of the node, so to make sure that we always keep the lowest`low[]`

time for each node we update the`low[]`

value while returning from DFS call. - When we visit a neighbor in the DFS call one of the three conditions will be true,
- If the neighbor is the parent node, then
*Continue to next neighbor*, because we don’t want to visit the node again which is already visited and the parent is already visited.

- If the neighbor is not a parent but already visited
*Reassign the low value of the current node with the minimum of*`low[]`

value of the current node and`disc[]`

value of neighbor.`low[current_node]`

= minimim_of`(low[current_node], disc[neighbour])`

- The reason why we did this is that there might be a possibility to get a less
`low[i]`

time for a current node`i`

and`low[i]`

is the lowest possible discovery time of`node i`

.

- Neighbour is not visited, of course,
**not a parent**as well- Make
`DFS`

call to the neighbor`DFS(neighbour)`

- While returning from
`DFS`

call, update`low[]`

value`low[current_node] = minimim_of(low[current_node], low[neighbour])`

, same as we discussed in the first step.

- Now it’s time to detect the articulation point
- If the current node is the parent node, (
`par[current_node] = -1`

), then count the number of`DFS`

calls made from the parent. If the count is greater than`1`

,*then the current node is an Articulation point*. - Because if it’s a parent node and count of
`DFS`

calls is greater than`1`

, then more than`1`

`DFS`

call is being made from the source node, which is only possible when source node is the only junction between two components of a graph. - If the current node is not the parent node, then check if (
`low[neighbout] >= disc[current_node]`

) if this is true then,*current node is an Articulation point*.

- If the current node is the parent node, (

- Make

- If the neighbor is the parent node, then

**Time Complexity of detecting Articulation Points**: If you closely observe we are only visiting each node once and in `depth-first-search`

manner. So the time complexity to detect the `articulation points`

in a graph is `O(V + E)`

, *which is the same as the time complexity of DFS traversal in a graph. V is the number of nodes and E is the number of edges in the graph.*

Below is a ** DFS tree** for the graph along with the discovery time and low value for each node.

Clearly **node 2** and it’s **neighbour 5**, * low[5] >= disc[2]*, so that mean

**node 2 is an Articulation point**and our algorithm returns true.

*Now let’s head back to Biconnected components, I promise things will be much easier now.*

## Biconnected Components

- For a given graph, a
`Biconnected Component`

is one of its subgraphs that is Biconnected. This means there is always a path between any two nodes in the component, even after removing any node from the component.

For example, for the graph given, it has 2 `bioconnected components`

.

`Biconnected components`

in a graph can be easily determined with the help of the same algorithm we used to detect the Articulation point. Remember we return true as soon as we detect an Articulation point, let’s take advantage of this fact.*We maintain a*.`stack`

of edges**Why only stack?**because we want**quick insertion and deletion operations**and stack provides both insertion and deletion in constant time. Each element in the stack will refer to an edge`U -> V`

, where`U`

is the source and`V`

is the destination.- Keep adding edges to the stack in the order they are visited and when an articulation point is detected i.e. say a node
`U`

has a child`V`

such that no node in the subtree rooted at`V`

has a back edge () then pop and print all the edges in the stack till the edge`low[V] >= disc[U]`

is found, as all those edges including the edge`U-V`

`U-V`

will form one.`biconnected component`

## Example of Biconnected Components Algorithm

- Consider the graph shown below, let’s do a dry run of the algorithm we discussed above.

- Suppose the source node is the node with the value
`1`

. First, we make a DFS call to this node with an empty stack. We mark`Node-1`

as visited, discovery time, and low time as`(1, 1)`

and now we have to make a DFS call to one of its unvisited children.`Node-1`

has two children(), suppose DFS call is then made to`Node-4`

and`Node-3`

`Node 4`

.`Node 4`

is marked visited with discovery time and low time as`(2, 2)`

and the edge from`Node-1`

to`Node-4`

is pushed into the stack. The stack now contains**one element**,

- Now the control is at the
`Node-4`

. It has two children (),`Node-1`

and`Node-2`

`Node-1`

is already visited so we make DFS call to`Node-2`

.`Node-2`

is then marked visited with discovery time and low time as`(3, 3)`

and the edge from`Node-4`

to`Node-2`

is pushed onto the stack. The stack now contains**two elements**,

- Now the control is at the
`Node-2`

. It has four children (),`Node-4`

,`Node-3`

,`Node-5`

and`Node-6`

`Node-4`

is already visited and is the parent of`Node-2`

so we make DFS call to`Node-3`

.`Node-3`

is then marked visited with discovery time and low time as`(4, 4)`

, and the edge from`Node-2`

to`Node-3`

is pushed into the stack. The stack now contains**three elements**,

- Now the control is at the node
`Node-3`

. It has two children (), both of the children are visited but`Node-1`

and`Node-2`

`Node-1`

is not the parent node for`Node-3`

, so we add the edge from`Node-3`

to`Node-1`

into the stack and backtrack to`Node-2`

. Also, we assign a new`low[]`

value to`Node-3`

that is the`low[]`

value of node`Node-1`

as`Node-1`

is already visited and not the parent node of`Node-3`

. The stack now contains**four elements**,

- Now we are again at
`Node-2`

, we make DFS call to its child`Node-5`

as it is unvisited.`Node-5`

is then marked visited with discovery time and low time as`(5, 5)`

. Also, the edge from`Node-2`

to`Node-5`

is pushed into the stack. Stack now contains**5 elements**,

- Control is at
`Node-5`

, it has two children (),`Node-2`

and`Node-5`

`Node-2`

is the parent and already visited we have no business to do there. DFS call is then made to`Node-6`

it is marked visited with discovery time and low values as`(6, 6)`

and the edge from`Node-5`

to`Node-6`

is added to the stack. Stack now contains**six elements**,

- Now the control is at
`Node-6`

, it has two children().`Node-2`

and`Node-5`

`Node-5`

is the parent node and already visited but`Node-2`

is not the parent node but it is already visited, so we mark the low value of`Node-6`

to discovery value of`Node-2`

that is. We also add the edge from`low[6] = disc[2] => 3`

`Node-6`

to`Node-2`

into the stack. Stack now contains**seven elements**,

- Now all the children of
`Node-6`

are visited, we then backtrack to`Node-5`

, here we see that the child`Node-6`

of`Node-5`

have less`low[]`

value than the`Node-6`

. We update the`low[]`

value of`Node-5`

to`low[]`

value of`Node-6`

. That is,.`low[5] = low[6] => 3`

- Now we backtrack to
`Node-2`

, this is the moment where we print out**first biconnected component**. Since, which is indeed a condition for`low[5] >= disc[2]`

**Articulation point**. We print the elements of the stack until we reach the edge`(2-5)`

. This pops`3`

elements from the stack and forms a connected component shown below,

- When all the nodes are visited starting from the source node DFS call return to the source node and finally the
`4`

elements left in the stack form another`Biconnected component`

. The two`Biconnected components`

in the graph are shown below,

## Implementation of Biconnected Components in C++

- In the main function, we take input of the number of nodes(
`n`

) and the number of edges(`m`

) in the graph. After that, we create the**adjacency list**to represent the graph. Once we are done with the input work, we create an object of class Solution. - This
`sol`

object has access to a public method of class`Solution`

`print_biconnected_component()`

. We simply call this method passing the graph and the number of nodes. The rest is the same as discussed in the algorithm above.

```
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int time = 1; // discovery time variable, it starts with 1 as discussed above
vector<bool> vis; // visited array
vector<int> par, disc, low; // arrays to keep track for parent, discovery time, low values
private:
// method to print stack till the top of the stack not equal to an edge
void printStackTill_UV(stack<pair<int, int>>& st, pair<int, int>& p) {
while(!st.empty()) {
cout << st.top().first << "-" << st.top().second <<", ";
if(st.top() == p) {
st.pop();
break;
}
st.pop();
}
cout << endl;
}
public:
void print_biconnected_component(vector<vector<int>>& graph, int& n) {
low.resize(n+1, 0); // mark the low value of each node is 0
vis.resize(n+1, false); // mark the visited array as false
par.resize(n+1, -1); // mark the parent of each node as -1
disc.resize(n+1, 0); // mark the discovery time of each node
// greaph can have multiple components, so we need to go to each
// node and apply DFS
for(int i=1; i<=n; i++)
{
// if the current is not previously visited
if(vis[i] == false)
{
stack<pair<int, int>> st; // stack of edges
DFS(i, graph, st); // call DFS
// print the stack when DFS call returns
while(!st.empty()) {
cout << st.top().first << "-" << st.top().second <<", ";
st.pop();
}
}
}
}
void DFS(int src, vector<vector<int>>& graph, stack<pair<int, int>>& st) {
disc[src] = low[src] = time; // mark the low time and discovery time
time++; // increment the time
vis[src] = true; // mark visited as true
int child = 0; // varible to keep count of DFS call made from source
vector<int> nbrs = graph[src]; // iterate over all neighbours
for(auto& nbr: nbrs)
{
pair<int, int> edge = {src, nbr}; // current edge
if(vis[nbr] == false) { // if the neighbour is not previously visited
child += 1;
par[nbr] = src; // mark the parent
st.push(edge); // push edge to stack
DFS(nbr, graph, st); // make DFS call
low[src] = min(low[src], low[nbr]); // update the low time
if(par[src] == -1 and child > 1) { // check for Articulation point, if it's true then print all edges
printStackTill_UV(st, edge);
}
if(par[src] != -1 and low[nbr] >= disc[src]) { // check for Articulation point, if it's true then print all edges
printStackTill_UV(st, edge);
}
}
else if(par[src] != nbr and disc[nbr] < low[src]) { // if the neighbour is previously visited
low[src] = disc[nbr]; // update the low value
st.push(edge); // push edge to stack
}
}
}
};
int main()
{
// Driver code
int n, m; cin >> n >> m;
vector<vector<int>> graph(n+1, vector<int>{});
for(int i=0; i<m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
Solution sol;
sol.print_biconnected_component(graph, n);
}
```

## Implementation of Biconnected Components in Java

```
import java.util.*;
public class Main{
// Pair class
static class Pair{
int x,y;
Pair(int x,int y){
this.x=x;
this.y=y;
}
}
// Discovery time variable, it starts with 1 as discussed above
static int time;
// Visited Array
static boolean visited[];
// Arrays to keep track for parent,
// discovery time, low values.
static int par[], disc[], low[];
static boolean isEqual(Pair p1, Pair p2){
return p1.x==p2.x&&p1.y==p2.y;
}
// Method to print stack till the top of
// the stack not equal to an edge
static void printStackTill_UV(Stack<Pair> st,
Pair p){
while(!st.isEmpty()){
System.out.print(st.peek().x+" - "+
st.peek().y+" ");
if(isEqual(st.peek(),p)){
st.pop();
break;
}
st.pop();
}
System.out.println();
}
static void printBiConnectedComponents(int n){
// Initialize all the variables like
// 1. time = 1
// 2. low - Array of size n+1 with all entries as 0.
// 3. visited - Boolean array of size n+1 with
// all elements as false
// 4. par - Array of size n+1 with all entries as -1.
time=1;
low=new int[n+1];
visited=new boolean[n+1];
disc=new int[n+1];
par=new int[n+1];
Arrays.fill(par, -1);
// Graph can have multiple components, so
// we need to go to each node and apply DFS
for(int i=1;i<=n;i++){
// If the current node is not previously visited
if(!visited[i]){
// Stack of edges
Stack<Pair> st=new Stack<>();
// Call DFS
DFS(i, st);
// Print the stack when DFS call returns
while(!st.isEmpty()){
System.out.print(st.peek().x+" - "+
st.pop().y+" ");
}
}
}
}
static void DFS(int src, Stack<Pair> st){
// mark the low time and discovery time,
// increment the time and mark src as visited
disc[src]=low[src]=time++;
visited[src]=true;
// Varible to keep count of
// DFS call made from source
int child=0;
// Iterate over all neighbours
for(int nbr:adj.get(src)){
// Current edge
Pair edge=new Pair(src, nbr);
// If the neighbour is not
// unvisited still.
if(!visited[nbr]){
child++;
// Mark the parent.
par[nbr]=src;
// Push into stack.
st.push(edge);
// Make DFS call
DFS(nbr, st);
// Update the low time
low[src]=Math.min(low[src], low[nbr]);
// Check for Articulation point, if it's true
// then print all edges
if((par[src]==-1&&child>1)||
(par[src]!=-1 && low[nbr]>=disc[src]))
printStackTill_UV(st, edge);
} else if(par[src]!=nbr &&
disc[nbr]<low[src]){
// if the neighbour is previously visited
// Update the low value.
low[src]=disc[nbr];
// Push edge to stack.
st.push(edge);
}
}
}
// Adjacency List.
static List<List<Integer>> adj;
// Method to add edge.
static void addEgde(int u, int v){
adj.get(u).add(v);
adj.get(v).add(u);
}
// Drive function.
public static void main(String args[]){
adj=new ArrayList<>();
int V=6;
for(int i=0;i<=V;i++)
adj.add(new ArrayList<>());
/*
Making the following graph
1
/ \
4 3
\ /
2
/ \
5-6
*/
addEgde(1,4);
addEgde(1,3);
addEgde(4,2);
addEgde(3,2);
addEgde(2,5);
addEgde(2,6);
addEgde(5,6);
printBiConnectedComponents(V);
System.out.println();
}
}
```

## Implementation of Biconnected Components in C

```
using System;
using System.Collections;
using System.Collections.Generic;
public class main{
// Pair class
class Pair{
public int x,y;
public Pair(int x,int y){
this.x=x;
this.y=y;
}
}
// Discovery time variable, it starts with 1 as discussed above
static int time;
// Visited Array
static bool[] visited;
// Arrays to keep track for parent,
// discovery time, low values.
static int[] par;
static int[] disc;
static int[] low;
static bool isEqual(Pair p1, Pair p2){
return p1.x==p2.x&&p1.y==p2.y;
}
// Method to print stack till the top of
// the stack not equal to an edge
static void printStackTill_UV(Stack<Pair> st,
Pair p){
while(st.Count!=0){
Console.Write(st.Peek().x+" - "+
st.Peek().y+" ");
if(isEqual(st.Peek(),p)){
st.Pop();
break;
}
st.Pop();
}
Console.WriteLine();
}
static void printBiConnectedComponents(int n){
// Initialize all the variables like
// 1. time = 1
// 2. low - Array of size n+1 with all entries as 0.
// 3. visited - bool array of size n+1 with
// all elements as false
// 4. par - Array of size n+1 with all entries as -1.
time=1;
low=new int[n+1];
visited=new bool[n+1];
disc=new int[n+1];
par=new int[n+1];
for(int i=0;i<=n;i++)
par[i]=-1;
// Graph can have multiple components, so
// we need to go to each node and apply DFS
for(int i=1;i<=n;i++){
// If the current node is not previously visited
if(!visited[i]){
// Stack of edges
Stack<Pair> st=new Stack<Pair>();
// Call DFS
DFS(i, st);
// Print the stack when DFS call returns
while(st.Count!=0){
Console.Write(st.Peek().x+" - "+
st.Pop().y+" ");
}
}
}
}
static void DFS(int src, Stack<Pair> st){
// mark the low time and discovery time,
// increment the time and mark src as visited
disc[src]=low[src]=time++;
visited[src]=true;
// Varible to keep count of
// DFS call made from source
int child=0;
// Iterate over all neighbours
foreach(int nbr in adj[src]){
// Current edge
Pair edge=new Pair(src, nbr);
// If the neighbour is not
// unvisited still.
if(!visited[nbr]){
child++;
// Mark the parent.
par[nbr]=src;
// Push into stack.
st.Push(edge);
// Make DFS call
DFS(nbr, st);
// Update the low time
low[src]=Math.Min(low[src], low[nbr]);
// Check for Articulation point, if it's true
// then print all edges
if((par[src]==-1&&child>1)||
(par[src]!=-1 && low[nbr]>=disc[src]))
printStackTill_UV(st, edge);
} else if(par[src]!=nbr &&
disc[nbr]<low[src]){
// if the neighbour is previously visited
// Update the low value.
low[src]=disc[nbr];
// Push edge to stack.
st.Push(edge);
}
}
}
// Adjacency List.
static List<List<int>> adj;
// Method to add edge.
static void addEgde(int u, int v){
adj[u].Add(v);
adj[v].Add(u);
}
// Drive function.
public static void Main(){
adj=new List<List<int>>();
int V=6;
for(int i=0;i<=V;i++)
adj.Add(new List<int>());
/*
Making the following graph
1
/ \
4 3
\ /
2
/ \
5-6
*/
addEgde(1,4);
addEgde(1,3);
addEgde(4,2);
addEgde(3,2);
addEgde(2,5);
addEgde(2,6);
addEgde(5,6);
printBiConnectedComponents(V);
Console.WriteLine();
}
}
```

**Output –**

```
6 - 2 5 - 6 2 - 5
3 - 1 2 - 3 4 - 2 1 - 4
```

**Time Complexity**: We are doing no fancy work except the Depth first Search. So the time complexity of this program will be, where V is the number of nodes and E is the number of edges. Which is same as the time complexity of`O(V + E)`

`Depth first search`

.**Space Complexity**: We are using total 5 arrays here namely**vis, disc, low, graph, par**. So the space complexity is. We also need a`O(5 * N)`

recursion stack space to make`O(N)`

`DFS`

calls. N is the number of nodes in the graph.

## Conclusion

- For a given graph,
*a*. A graph can have many`Biconnected Component`

is one of its subgraphs which is Biconnected`biconnected components`

. `Biconnected components`

are strongly dependent on Articulation points.*A graph with no articulation point forms a single*.`biconnected component`

- Stack is used along with the algorithm to find the articulation point. We keep on adding the edges into the stack as we visit them in the DFS call until we hit the articulation point.
- Once the articulation point is detected, we pop the edges from the stack till we reach the edge where the parent has lesser or equal discovery time than the neighbor. All of the edges popped till now form a
`biconnected component`

. - The time complexity is the same as the time complexity of
*Depth-first search*in a graph, that is.`O(V + E)`