315

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks.
For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.

There are two ways to solve articulation point problems.

A) For every vertex v, do following

…..a) Remove v from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add v back to the graph

For this algorithm time complexity is O(V*(V+E))

#include <iostream>
#include <cstdio>
#include <vector>
#include <sstream>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

vector<int> gr[105];
bool visit[105];
int N;

int bfs(int s)
{
	visit[s]=1;
	queue<int> q;
	q.push(s);

	while(!q.empty())
	{
		int a = q.front();
		q.pop();
		for(int i=0;i<gr[a].size();i++)
		{
			if(!visit[gr[a][i]])
			{
				visit[gr[a][i]]=1;
				q.push(gr[a][i]);
			}
		}
	}

	for(int i=1;i<=N;i++)
	{
		if(visit[i]==0)
		return 1;
	}
	return 0;
}

int main()
{
	int n,a;
	string s;

	while(scanf("%d",&N),N)
	{
		getchar();
		if(N==1)
		{
			cin>>a;
			cout<<0<<"\n";
			continue;
		}
		for(int i=0;i<105;i++)
		{
			gr[i].clear();
			visit[i]=false;
		}
		while(getline(cin,s))
		{
			stringstream ss;
			ss<<s;
			ss>>n;
			if(n==0)
			break;

			while(ss>>a)
			{
				gr[n].push_back(a);
				gr[a].push_back(n);
			}
		}
		int cnt=0;

		for(int i=2;i<=N;i++)
		{
			memset(visit,0,sizeof(visit));
			visit[i]=1;
			if(bfs(1))
			cnt+=1;
		}
		memset(visit,0,sizeof(visit));
		visit[1]=1;
		if(bfs(2))
			cnt+=1;
		cout<<cnt<<"\n";
	}
	return 0;
}

B)Linear time algorithm :: Tarjan’s algorithm

Time complexity O(V+E).It is a DFS based solution. Articulation point connects two (or more) sub graphs. In a DFS tree a vertex u is articulation point iff it follows one of the following two rules.

a)u is root of DFS tree and it has at least two children.

b)If u is not root of DFS tree and it has a child v such that no vertex in sub tree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.

#include <iostream>
#include <cstdio>
#include <vector>
#include <sstream>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

vector<int> gr[105];
bool visit[105];
int N;
int low[105];
int disc[105];
int par[105];
bool ap[105];

void cutvertex(int u)
{
	static int disc_time = 0;
	low[u]=disc[u]=disc_time++;
	int child = 0;
	visit[u]=1;
	for(int i=0;i<gr[u].size();i++)
	{
		int v = gr[u][i];
		if(visit[v]==0)
		{
			child++;
			par[v]=u;
			cutvertex(v);
			low[u]=min(low[u],low[v]);

			// u is an articulation point in following cases
            // (1) u is root of DFS tree and has two or more chilren.
            if(par[u]==-1 && child>1)
            {
            	ap[u]=true;
            }
            // (2) If u is not root and low value of one of its child is more
            // than discovery value of u.
            else if(par[u]!=-1 && low[v]>=disc[u])
            {
            	ap[u]=true;
            }
		}
		else if(v!=par[u])
			low[u]=min(low[u],disc[v]);
	}
}
int main()
{
	int n,a;
	string s;

	while(scanf("%d",&N),N)
	{
		getchar();
		if(N==1)
		{
			cin>>a;
			cout<<0<<"\n";
			continue;
		}
		for(int i=0;i<105;i++)
		{
			gr[i].clear();
			visit[i]=false;
		}
		while(getline(cin,s))
		{
			stringstream ss;
			ss<<s;
			ss>>n;
			if(n==0)
			break;

			while(ss>>a)
			{
				gr[n].push_back(a);
				gr[a].push_back(n);
			}
		}

		for(int i=0;i<105;i++)
		{
			par[i]=-1;low[i]=0;disc[i]=0;ap[i]=0;
		}

		for(int i=1;i<=N;i++)
		{
			if(visit[i]==0)
				cutvertex(i);
		}
		int articulate_pnt = 0;
		for(int i=1;i<=N;i++)
		{
			if(ap[i])
			articulate_pnt++;
		}
		cout<<articulate_pnt<<"\n";
	}
	return 0;
}