Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment