Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

ARTICULATION POINTS IN A GRAPH

articulation point is a vertex of a graph if this vertex get  out of the graph ,then the graph will get disconnected.

spoj question in articulation point http://www.spoj.com/problems/SUBMERGE/

code:-

#include<bits/stdc++.h>

using namespace std;

vector<int>a[100000];
int arr[100000],parent[100000],low[100000],visited[100000],tim=1;
set<int> s;


void dfs(int st)
{
arr[st]=tim++;
low[st]=arr[st];
visited[st]=1;

int child=0;

 for(int i=0;i<a[st].size();i++)
 {
  if(visited[a[st][i]]==0)
  {
    child++;
    parent[a[st][i]]=st;

    dfs(a[st][i]);

    ///lower part of this code starts executing for leaf

    low[st]=min(low[st],low[a[st][i]]);                  ///"low" child ke karan change ho raha hai

    if(parent[st]==INT_MAX && child>1) s.insert(st);       ///dfs root ke liye articulation ka condition
   
//cout<<st<<" is articulation point"<<endl;

    if(low[a[st][i]]>=arr[st] && parent[st]!=INT_MAX ) s.insert(st);   ///ye general
    //cout<<st<<" is articulation point"<<endl;
  }

   else if(visited[a[st][i]]==1 && parent[st]!=a[st][i])   ///ye bata raha hai backage st ka
    low[st]=min(low[st],arr[a[st][i]]);                   /// iss condition me low aise upadate hoga
                                                         ///"low" backage ke karan change ho raha hai
 }
}

int main()
{
 int i,j;
 while(1)
 {
 int v,e,p,q;
 cin>>v>>e;

 if(v==0 && e==0)
 break;

 for(i=0;i<e;i++)
 {
  cin>>p>>q;
  a[p].push_back(q);
  a[q].push_back(p);
 }
 tim=1;
  parent[1]=INT_MAX;
  dfs(1);
  cout<<s.size()<<endl;

  s.clear();
  for(i=0;i<100000;i++)
  a[i].clear();

  for(i=0;i<100000;i++)
  parent[i]=arr[i]=low[i]=visited[i]=0;
 }
return 0;
}

------------------------------------------------------------0----------------------------------------------------------------------------------------------------------------------0-----0---------------------------------------------------------------------------------------------------------------------0---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Adjacency matrix solution 

#include<bits/stdc++.h>

using namespace std;

int a[100][100],arr[1000],parent[1000],low[1000],visited[1000],tim=1,v;

void dfs(int st)

{

arr[st]=tim++;

low[st]=arr[st];

visited[st]=1;

int child=0;

 for(int i=0;i<v;i++)

 {

  if(a[st][i]==1 && visited[i]==0)

  {

    child++;

    parent[i]=st;

    dfs(i);

    ///lower part of this code starts executing for leaf

    low[st]=min(low[st],low[i]);                  ///"low" child ke karan change ho raha hai

    if(parent[st]==INT_MAX && child>1)            ///dfs root ke liye articulation ka condition

    cout<<st<<" is articulation point"<<endl;

    if(low[i]>=arr[st] && parent[st]!=INT_MAX )   ///ye general

    cout<<st<<" is articulation point"<<endl;

  }

  else if(a[st][i]==1 && visited[i]==1 && parent[st]!=i)   ///ye bata raha hai backage st ka

    low[st]=min(low[st],arr[i]);                          /// iss condition me low aise upadate hoga

                                                         ///"low" backage ke karan change ho raha hai

 }

}

int main()

{

 int i,j;

 cin>>v;

 for(i=0;i<v;i++)

  for(j=0;j<v;j++)

   cin>>a[i][j];

  parent[0]=INT_MAX;

  dfs(0);

return 0;

}