Bipartite graph check for UVa problem "11080 - Place the Guards"

BipartiteGraphCkeck.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <utility>
using namespace std;
int N, M;
vector<int> G[200];
bool visited[200];
int color[200];
vector<int> answers;
int BFS(int root)
{
    queue<int> Q;
    bool isBipartite = true;
    color[root] = 0;
    visited[root] = true;
    Q.push(root);
    int totalSize = 0;
    int c = 0;
    while(!Q.empty())
    {
        int current = Q.front(); Q.pop();
        if(color[current] == 0) ++c;
        ++totalSize;
        //cout<<"current: "<<current<<", color: "<<color[current]<<", currentCount: "<<c<<", total: "<<totalSize<<endl;
        for(int i = 0; i < G[current].size(); ++i)
        {
            int child = G[current][i];
            if(!visited[child])
            {
                visited[child] = true;
                color[child] = 1 - color[current];
                Q.push(child);
            }
            else if(color[child] == color[current])
            {
                isBipartite = false;
                break;
            }
        }
    }
    if(isBipartite) return max(1, min(c, totalSize - c));
    else return -1;
}
void read()
{
    for(int i = 0; i < 200; ++i) G[i].clear();
    memset(color, -1, sizeof color);
    memset(visited, 0, sizeof visited);
    //now do shit
    cin >> N >> M;
    for(int i = 0; i < M; ++i)
    {
        int from, to;
        cin >> from >> to;
        G[from].push_back(to);
        G[to].push_back(from);
    }
    int sum = 0;
    bool possible = false;
    for(int i = 0; i < N; ++i)
    {
        if(!visited[i])
        {
            int res = BFS(i);
            if(res == -1)
            {
                possible = false;
                break;
            }
            else
            {
                possible = true;
                sum += res;
            }
        }
    }
    //cout<<"SUM IS: "<<sum<<endl;
    if(possible) answers.push_back(sum);
    else answers.push_back(-1);
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
        read();
    }
    for(int i = 0; i < T; ++i) cout<<answers[i]<<'\n';
    return 0;
}
/*
2
4 2
0 1
2 3
5 5
0 1
1 2
2 3
0 4
3 4
*/