UVa 11080 - Place the Guards

/*

    Accepted

    Algorithm: BFS

    Check whether the given graph is Bipartite or not. If not then put -1 otherwise find
    the minimum number of guards. Note that, single connected component is needed minimum one guard.

*/

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

#define sf scanf
#define pf printf
#define psb push_back
#define fast ios_base::sync_with_stdio(false)

const int high = 505;
const int red = 1;
const int blue = 0;
const int white = -1;
bool bipartite = true;

vector<int>adj[high];
int guards = 0 , color[high] , count_red = 0 , count_blue = 0;

void CLR()
{
    for(int i=0; i<high; i++)
    {
        adj[i].clear();
        color[i] = white;
    }

    bipartite = true;
    count_blue = 0;
    count_red = 0;
    guards = 0;
}

void BFS(int s)
{
    color[s] = red;
    queue<int>Q;

    Q.push(s);

    count_red+=1;

    while(!Q.empty() && bipartite)
    {
        int u = Q.front();
        Q.pop();

        int sze = adj[u].size();

        for(int i=0; i<sze; i++)
        {
            int v = adj[u][i];

            if(color[u] == color[v])
            {
                bipartite = false;
                return;
            }

            if(color[v] == white)
            {
                color[v] = 1-color[u]; // blue colored adjacent
                Q.push(v);
                color[v] == 0 ? count_blue+=1 : count_red+=1;
            }
        }
    }
}

int main()
{
    fast;
    int v , i , e , f , t , test;
    sf("%d", &test);

    while(test--)
    {
        CLR();

        sf("%d %d", &v , &e);

        for(i=0; i<e; i++)
        {
            sf("%d %d", &f , &t);

            adj[f].psb(t);
            adj[t].psb(f);
        }

        for(i=0; i<v; i++)
        {
            if(color[i] == white)
            {
                count_blue = 0;
                count_red = 0;
                BFS(i);
                int mn = min(count_red, count_blue);
                guards += max(1 , mn); // single connected component has one color and its needed
                // a guard
            }
        }

        printf("%d\n", !bipartite ? -1 : guards);
    }

    return 0;
}