Articulation Point

Problem Link:
https://www.spoj.com/problems/SUBMERGE/en/

Hints: Find how many articulation point in the graph

Solution

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e4+4;
vector<int>vec[maxn];
bool visit[maxn];
int parent[maxn];
int low[maxn];
set<int>ap;
int disc[maxn];
int timee;
void ArticulationPoint(int u)
{
    int child=0;
    visit[u]=1;
    disc[u]=low[u]=++timee;
    for(int i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if(visit[v]==0)
        {
            child++;
            parent[v]=u;
            ArticulationPoint(v);
            low[u]=min(low[u],low[v]);
            if(parent[u]==-1&&child>1)
                ap.insert(u);
            if(parent[u]!=-1&&low[v]>=disc[u])
                ap.insert(u);
        }
        else if(v!=parent[u])
            low[u]=min(low[u],disc[v]);
    }
}
int main()
{
    //freopen("t.txt","r",stdin);
    int n,m,u,v;
    while(scanf("%d%d",&n,&m))
    {
        if(!n&&!m)
            break;
        memset(parent,-1,sizeof parent);
        memset(visit,0,sizeof visit);
        for(int i=0; i<n+1; i++)
            vec[i].clear();
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        for(int i=0; i<n; i++)
        {
            if(visit[i]==0)
            {
                timee=0;
                ArticulationPoint(i);
            }
        }
        printf("%d\n",ap.size());
        ap.clear();
    }
}