Last Updated: 2 Jul, 2021

Biconnected Components

Hard

Asked in companies

Solve now

Problem statement

You are given an undirected graph of N nodes and M edges. You are required to find out the number of bi-connected components of the graph. We donot count an isolated vertex as a biconnected component

For Example:

alt text

Consider the following graph

4 4
1 3
1 2
2 3
3 4

The graph has two bi-connected components 

1 - 2, 2 - 3, 3 - 1

3 - 4

Hence the output is 2.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

Each test case contains a line containing two integers ‘N’ and ‘M’. Then ‘M’ lines follow: 
Each line contains 2 space-separated integers ‘u’ and ‘v’ which means that there is an edge between ‘u’ and  ‘v’.

Output Format:

For each test case, output a single line containing one integer - the number of bi-connected components in the graph.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N, M <= 10^4
1 <= u, v <= N

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

Firstly you can read about bi-connected components here.

Since we need to make sure that our biconnected component should be connected and does not contain any articulation point, we maintain a stack of edges while performing DFS traversal of the graph and push the edges we traverse during the DFS into the stack.

As we backtrack from the DFS traversal, say currently we are at edge v-to, we check if v is an articulation point i.e low[to] >= disc[v], if v is an articulation point then we pop the edges from the stack until the top of the stack is ‘v-to’ and include ‘v-to’ too. The popped set of edges will form one biconnected component of the given graph.

Algorithm:

function biconnectedComponents(N, M, edges) takes the graph as input and returns the number of biconnected components in the graph.

Call the dfs function for every unvisited node in the graph.
Whenever a vertex is visited first time initialize the discovery time and the ‘low’ time of that vertex to the current time counter and increase it.
For each vertex v in the adjacency list of u:
1. if it is not visited, push the edge u - v in the stack and call the dfs for v.
  1. check if the subtree of v has a connection to one of the ancestors by updating low[u] = min(low[u], low[v]).
  2. If u is an articulation point, pop all the edges from the stack until this edge and increase the count of biconnected components by 1.
2. If v is already visited, then update the low[u] time with the discovery time of v and push the edge into the stack.
If the stack is not empty increase the number of components by 1.
Finally, return the number of biconnected components in the graph.

Solve now