articulation point in a graph

Solutions on MaxInterview for articulation point in a graph by the best coders in the world

showing results for - "articulation point in a graph"
Mats
08 Oct 2018
1//Articulation point is a point in the graph on whose removal graph is broken into components
2//striver graph series
3//Do check u__code on youtube
4#include<bits/stdc++.h>
5using namespace std;
6void addedge(vector<int>adj[],int u,int v)
7{
8    adj[u].push_back(v);
9    adj[v].push_back(u);
10}
11void dfs(int node,int parent,vector<int>&visited,vector<int>&low,vector<int>&tin,vector<int>adj[],int timer,vector<int>&isarticulate)
12{
13    visited[node]=1;
14    low[node]=tin[node]=timer++;
15    int child=0;
16    for(auto it:adj[node])
17    {
18        if(it==parent)
19            continue;
20        if(!visited[it])
21        {
22            dfs(it,node,visited,low,tin,adj,timer,isarticulate);
23            low[node]=min(low[node],low[it]);
24            if(low[it]>=tin[node]&&parent!=-1)
25            {
26                isarticulate[node]=1;
27            }
28        }
29        else
30        {
31            low[node]=min(low[node],tin[it]);
32        }
33    }
34    if(parent==-1&&child>1)
35        isarticulate[node]=1;
36}
37int main()
38{
39    int vertex,edges;
40    cout<<"ENTER THE VERTEX AND EDGES:"<<endl;
41    cin>>vertex>>edges;
42    vector<int>adj[vertex];
43    int a,b;
44    cout<<"ENTER THE LINKS:"<<endl;
45    for(int i=0;i<edges;i++)
46    {
47        cin>>a>>b;
48        addedge(adj,a,b);
49    }
50    vector<int>tin(vertex,-1);
51    vector<int>low(vertex,-1);
52    vector<int>visited(vertex,0);
53    vector<int>isarticulate(vertex,0);
54    int timer=0;
55    for(int i=0;i<vertex;i++)
56    {
57        if(!visited[i])
58        {
59            dfs(i,-1,visited,low,tin,adj,timer,isarticulate);
60        }
61    }
62    for(int i=0;i<vertex;i++)
63    {
64        if(isarticulate[i]==1)
65        {
66            cout<<i<<" ";
67        }
68    }
69    return 0;
70}
71