articulation point in a graph
//Articulation point is a point in the graph on whose removal graph is broken into components
//striver graph series
//Do check u__code on youtube
#include<bits/stdc++.h>
using namespace std;
void addedge(vector<int>adj[],int u,int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs(int node,int parent,vector<int>&visited,vector<int>&low,vector<int>&tin,vector<int>adj[],int timer,vector<int>&isarticulate)
{
visited[node]=1;
low[node]=tin[node]=timer++;
int child=0;
for(auto it:adj[node])
{
if(it==parent)
continue;
if(!visited[it])
{
dfs(it,node,visited,low,tin,adj,timer,isarticulate);
low[node]=min(low[node],low[it]);
if(low[it]>=tin[node]&&parent!=-1)
{
isarticulate[node]=1;
}
}
else
{
low[node]=min(low[node],tin[it]);
}
}
if(parent==-1&&child>1)
isarticulate[node]=1;
}
int main()
{
int vertex,edges;
cout<<"ENTER THE VERTEX AND EDGES:"<<endl;
cin>>vertex>>edges;
vector<int>adj[vertex];
int a,b;
cout<<"ENTER THE LINKS:"<<endl;
for(int i=0;i<edges;i++)
{
cin>>a>>b;
addedge(adj,a,b);
}
vector<int>tin(vertex,-1);
vector<int>low(vertex,-1);
vector<int>visited(vertex,0);
vector<int>isarticulate(vertex,0);
int timer=0;
for(int i=0;i<vertex;i++)
{
if(!visited[i])
{
dfs(i,-1,visited,low,tin,adj,timer,isarticulate);
}
}
for(int i=0;i<vertex;i++)
{
if(isarticulate[i]==1)
{
cout<<i<<" ";
}
}
return 0;
}