LightOJ Back to Underworld 1009 Solution

   Solution in C++: 

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

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

#include<bits/stdc++.h>

using namespace std;

const int  limit=20005;

const int  black = 1;

const int  red  = 2;

const int  white = 0;

vector<int>adj[limit];

int n,t,ts,i,j,ans=0,u,v;

int color[limit],vampire=0,lykan=0;

void adj_clear()

{

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

    {

        adj[i].clear();

    }

}

void bfs(int s)

{

    queue<int>q;

    color[s]=black;

    vampire++;

    q.push(s);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        for(int i=0; i<adj[u].size(); i++)

        {

            int v = adj[u][i];

            if(color[v]==white)

            {

                q.push(v);

                if(color[u]==black)

                {

                    color[v] = red;

                    lykan++;

                }

                else

                {

                    color[v] = black;

                    vampire++;

                }

            }

        }

    }

}

int main()

{

    cin>>t;

   for(int k=1;k<=t;k++)

    {

        vampire = 0;

        lykan = 0;

        ans = 0;

        ts=0;

        adj_clear();

        memset(color,0,sizeof color);

        cin>>n;

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

        {

            cin>>u>>v;

            adj[u].push_back(v);

            adj[v].push_back(u);

        }

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

        {

            if((!adj[i].empty())&&(color[i] == white))

            {

                vampire = 0;

                lykan = 0;

                bfs(i);

                ans += max(vampire, lykan);

            }

        }

        printf("Case %d: %d\n",k , ans);

    }

}