Biconnected Components - GeeksforGeeks
we will see how to find biconnected component in a graph using algorithm by John Hopcroft and Robert Tarjan.
If there is no Articulation Point in graph, then graph is biconnected and so there will be one biconnected component which is the graph itself.
Read full article from Biconnected Components - GeeksforGeeks
we will see how to find biconnected component in a graph using algorithm by John Hopcroft and Robert Tarjan.
Idea is to store visited edges in a stack while DFS on a graph and keep looking for Articulation Points (highlighted in above figure). As soon as an Articulation Point u is found, all edges visited while DFS from node u onwards will form one biconnected component. When DFS completes for one connected component, all edges present in stack will form a biconnected component.
If there is no Articulation Point in graph, then graph is biconnected and so there will be one biconnected component which is the graph itself.
// A recursive function that finds and prints strongly connected// components using DFS traversal// u --> The vertex to be visited next// disc[] --> Stores discovery times of visited vertices// low[] -- >> earliest visited vertex (the vertex with minimum// discovery time) that can be reached from subtree// rooted with current vertex// *st -- >> To store visited edgesvoid Graph::BCCUtil(int u, int disc[], int low[], list<Edge> *st, int parent[]){ // A static variable is used for simplicity, we can avoid use // of static variable by passing a pointer. static int time = 0; // Initialize discovery time and low value disc[u] = low[u] = ++time; int children = 0; // Go through all vertices adjacent to this list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // v is current adjacent of 'u' // If v is not visited yet, then recur for it if (disc[v] == -1) { children++; parent[v] = u; //store the edge in stack st->push_back(Edge(u,v)); BCCUtil(v, disc, low, st, parent); // Check if the subtree rooted with 'v' has a // connection to one of the ancestors of 'u' // Case 1 -- per Strongly Connected Components Article low[u] = min(low[u], low[v]); //If u is an articulation point, //pop all edges from stack till u -- v if( (disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u]) ) { while(st->back().u != u || st->back().v != v) { cout << st->back().u << "--" << st->back().v << " "; st->pop_back(); } cout << st->back().u << "--" << st->back().v; st->pop_back(); cout << endl; count++; } } // Update low value of 'u' only of 'v' is still in stack // (i.e. it's a back edge, not cross edge). // Case 2 -- per Strongly Connected Components Article else if(v != parent[u] && disc[v] < low[u]) { low[u] = min(low[u], disc[v]); st->push_back(Edge(u,v)); } }} // The function to do DFS traversal. It uses BCCUtil()void Graph::BCC(){ int *disc = new int[V]; int *low = new int[V]; int *parent = new int[V]; list<Edge> *st = new list<Edge>[E]; // Initialize disc and low, and parent arrays for (int i = 0; i < V; i++) { disc[i] = NIL; low[i] = NIL; parent[i] = NIL; } for (int i = 0; i < V; i++) { if (disc[i] == NIL) BCCUtil(i, disc, low, st, parent); int j = 0; //If stack is not empty, pop all edges from stack while(st->size() > 0) { j = 1; cout << st->back().u << "--" << st->back().v << " "; st->pop_back(); } if(j == 1) { cout << endl; count++; } }}