Spoj SUBMERGE - Submerging Islands Solution

 

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

 Solution in C++: 

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

const int MAX_NODE = 100009;

vector <int> graph[ MAX_NODE ];

int low[ MAX_NODE ], discover[ MAX_NODE ], visit[ MAX_NODE ], node, edge, discover_time;

int isArticulationPoint[ MAX_NODE ];

void dfs( int node, int parnt )

{

    low[node] = discover[node] = discover_time++;

    visit[node] = 1;

    int sz = graph[node].size();

    int child = 0;

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

    {

 

        int nextNode = graph[node][i];

        if( parnt == nextNode ) continue;

        if( visit[nextNode] == 0 )

        {

 

            child++;

            dfs(nextNode, node );

            low[node] = min( low[node], low[nextNode]); // min value check with tree edge

            // root node condition

            if( parnt == -1 && child > 1 )

            {

                isArticulationPoint[node] = 1;

 

            }

            else if( parnt != -1 && low[nextNode] >= discover[node])

            {

 

                isArticulationPoint[node] = 1;

            }

        }

        else

        {

 

            low[node] = min( low[node], discover[nextNode] );// min value check with back edge

        }

 

    }

}

int main()

{

    while(cin >> node >> edge)

    {

        int  count=0;

        if(node==0&&edge==0)

            break;

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

        {

            graph[i].clear();

            visit[i] = 0;

            isArticulationPoint[i] = 0;

        }

        discover_time = 1;

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

        {

            int u, v;

            cin >> u >> v;

            graph[u].push_back(v);

            graph[v].push_back(u);

        }

        for( int i = 1 ; i <= node ; i++ )

        {

            if( visit[i] == 0 ) dfs( i, -1 );

        }

        for( int i = 1; i <= node ; i++ )

        {

            if( isArticulationPoint[i] == 1 )

            {

                count++;

            }

        }

        cout<< count<<endl;

    }

    return 0;

}