Introduction to competitive programming

Articulation Points in a Graph

A node in a undirected graph is said to be an articulation point iff on removing the node disconnects the graph. Articulation Points are Vulnerabilities which on failure spits the network in to two or more components.

In the above graph on removing vertex A,B and G it will disconnect the graphs and hence they are Articulation Points.
In our Algorithm we use DFS to find the articulation points.Applying DFS on given graph we will get the DFS tree.
A vertex u in parent of vertex v,if u is adjacent to v i.e u is adjacent and discovered earlier than v.A leaf of DFS tree is never an articulation point
In DFS tree a vertex u is said to be an articulation point if any one of the following condition satisfies.
(a)u is the root of tree and it has more than one children.(Up on removing this vertex two disconnected components are formed).
(b)If any child of a node does not have back_edge to ancestor of its parent,then on removing disconnects the graph.
Handling first case is easy for every node count the child,if the node is the root and it have more than two children then it is the articulation point.
Second case is tricky.So we maintain a disc[] array to store the discovery time of each vertex.For every vertex rooted with u we need to find the earliest visited vertex so we maintain another array low[].

Here is the C++ implementation of above Algorithm

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 102
vector<vector<int> >G(MAX);
int parent[MAX],low[MAX],disc[MAX],timer=0;
bool vis[MAX],ap[MAX];
void reset()
{
	for(int i=0;i<MAX;i++)
	{
		G[i].clear();
		vis[i]=false;
		ap[i]=false;
		parent[i]=-1;
	}
}
void dfs(int u)
{
	int child=0;
	vis[u]=true;
	disc[u]=low[u]=timer++;
	for(int i=0;i<G[u].size();i++)
	{	
 
		int v=G[u][i];
		if(!vis[v])
		{
			child++;
			parent[v]=u;
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(parent[u]==-1 and child>1)
			{
			ap[u]=true;
			}
			if(parent[u]!=-1 and low[v]>=disc[u])	
			{	
			ap[u]=true;
			}
		}
		else if(v!=parent[u])
		{
			low[u]=min(low[u],disc[v]);
		}
	}
}
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	reset();
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	cout<<"Articulation Points in Graph are \n";
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
		dfs(i);
	}
	for(int i=0;i<n;i++)
	{
		if(ap[i])
		cout<<i<<" ";
	}
	cout<<endl;
}