1009 - Back to Underworld LightOJ

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>

using namespace std;

#define ll long long int

ll BFS()
{
    ll u, v, n, t = 0;
    cin >> n;
    queue<ll> q;
    vector<ll> vc[100007];
    int race[100007] = {};
    ll vam=0, lyk=0;

    while (t<n)
    {
        cin >> u >> v;
        vc[u].push_back(v);
        vc[v].push_back(u);
        t++;
    }
    ll ans = 0 ;
/*The next line is used for this reason - The graph can be disconnected. We have to check it and count it. We can use map for it. But as it's an easy one , it didn't create any problem with time complexity. */
    for(ll idx = 1 ; idx< 100007 ; idx++)
    {
        if(vc[idx].size()!=0 && race[idx] == 0)
        {

            vam = 0 ;
            lyk = 0 ;

/**explaination: Look, here we don't care about if the fighter is a Vampire of Lykan, we only care the maximum
number of fighters of a certain kind. We have to check their value in every step , in every graph traversing (as they can be disconnected). So, the values of vam , lyk has to be set to '0' in the beginning of every step. */

            race[idx] = 1;
            vam++ ;
            q.push(idx);
            while (!q.empty())
            {
                ll node;
                node = q.front();
                q.pop();

                for (ll i = 0; i < vc[node].size(); i++)
                {
                    if (race[vc[node][i]] == 0)
                    {
                        if (race[node] == 1)
                        {
                            race[vc[node][i]] = 2;
                            lyk++;
                        }
                        else if (race[node] == 2)
                        {
                            race[vc[node][i]] = 1;
                            vam++;
                        }
                        q.push(vc[node][i]);
                    }
                }
            }
            ans += max(vam, lyk) ;
/* See , here is the main trick. You have to maximize the number of one kind. Suppose you have taken 1 as vampire and 2 as lykan.
But it doesn't really matter what have you taken as Lyk or Vam. You just have to get the maximized result at any graph.Because if we take 2 as vam and 1 as lyk then if the result maximizes , then it's our answer. so we have to check it in every step. */
        }
    }

    return ans;
}

int main()
{
//    freopen("out.txt","w", stdout);
    int T, t = 0;
    cin >> T;
    ll ans;

    while (T--)
    {
        ans = BFS();
        printf("Case %d: %lld\n",t+1,ans );
        t++;
    }
    return 0;
}