Last active
December 26, 2019 08:52
-
-
Save yashrsharma44/0997403ddfee6fe276f268cca11d06b0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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