articulation.cpp

#include <bits/stdc++.h>
#define MAX_VAL 40000
using namespace std;

/*

 Code for calculation of articulation point and bridges
 We use dp array for calculating the back edges over u(parent) -> v(child) edge
 dp[u] = # back-edge going up + # back-edge going down - Sum of dp[child] where child-> child of u(i.e. v)

*/

// Basic initialisation
vector<int> dp(MAX_VAL, 0);
vector<int> lvl(MAX_VAL, 0);
vector<int> adj[MAX_VAL];
// Bridge Count
int bcount = 0;
set<int> artset;


void dfs(int parent){
	dp[parent] = 0;
	for(int child : adj[parent]){

   		if(lvl[child] == 0) /* Parent - Child edge*/
   		{
		    lvl[child] = lvl[parent] + 1;
		 //    Traverse the child and update the dp
		    dfs(child);

		    dp[parent] += dp[child];
		} 
		else if(lvl[child] < lvl[parent]) /*Upwards back edge*/
		{
		    dp[parent]++;
		}
		else if(lvl[child] > lvl[parent]) /*Downwards back edge*/
		{
		    dp[parent]--;
		}
 	}

	// Exclude the parent - child edge
	dp[parent]--;

	if(dp[parent] == 0 && lvl[parent] > 1){
		bcount += 1;
	}
}

void dfs_count(int parent, vector<bool> &visited, int lvl_max){

	visited[parent] = true;
 
	for(int child : adj[parent]){
	
  	/*If dp[child] = 0 then it contains a bridge, add both the parent and child*/
								/*For excluding the leaf vertices*/
		if(!visited[child] && lvl[parent] > 1 && dp[child]==0 && lvl[child] != lvl_max){
			artset.insert(child);
			artset.insert(parent);
		}

		if(!visited[child]){
			dfs_count(child, visited, lvl_max);
		}
  
	}
 
}

int main(){

	int vcount, ecount;
	cout<<"Enter the number of vertices and edges"<<endl;
	cin>>vcount>>ecount;

	cout<<"Enter the u->v pair"<<endl;
	for(int i=0;i<ecount;i++){
		int uu, vv;
		cin>>uu>>vv;
		adj[uu].push_back(vv);
		adj[vv].push_back(uu);
	}

	dfs(1);
	int lvl_max = -1;
	for(int el : lvl){
		lvl_max = max(lvl_max, el);
	}

	vector<bool> visited(vcount, false);
	dfs_count(1, visited, lvl_max);
	
	cout<<"BRIDGE Count : "<<bcount<<endl;
	cout<<"ARTICULATION POINT"<<endl;
	
	for(auto el = artset.begin(); el!=artset.end(); el++){
		cout<<*el<<" ";
	}
	cout<<endl;

}