Uva 11080 Solution

#include<bits/stdc++.h>

#define White 1

#define Black 2

#define N 210

using namespace std;

int node, edge, a[N][N], c[N], white, black, result;

bool check(int start)

{

c[start] = 1;

queue<int>q;

q.push(start);

white = black = 0;

while(!q.empty())

{

int x = q.front();

q.pop();

if(c[x] == White)

white++;

if(c[x] == Black)

black++;

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

{

if(a[x][i] == 1 && c[i] == 0)

{

if(c[x] == Black)

c[i] = White;

else if(c[x] == White)

c[i] = Black;

q.push(i);

}

if(a[x][i] == 1 && c[x] == c[i])

return false;

}

}

return true;

}

bool Bipartite()

{

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

{

if(c[i] == 0)

{

if(check(i) == false)

return false;

result = result + max(min(white, black), 1);

}

}

return true;

}

void clear1()

{

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

{

c[i] = 0;

for(int j=0;j<N;j++)

{

a[i][j] = 0;

}

}

}

int main()

{

int t;

cin >> t;

while(t--)

{

result = 0;

cin >> node >> edge;

clear1();

int n1, n2;

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

{

cin >> n1 >> n2;

a[n1][n2] = 1;

a[n2][n1] = 1;

}

if(Bipartite() == true)

{

cout << result << "\n";

}

else

cout << "-1" << "\n";

}

return 0;

}