Uva : 11080 :: Place the Guards

Problem : Please find the problem here.
Summary : Here if the given graph is not bipartite there cannot be any guards placed in any junction, so the answer in this case is just -1. On the other hand if the graph is Bipartite we have to output minimum number of junctions that connects all the other junctions (for all the connected components).
Code: Used dfs to traverse all the connected components and returned if the graph is Bipartite or not. Also counted the minimum number of vertices(juntions) which connects all the other vertices.

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

const int mxN = 200;
int n, m, c[mxN], r, b;
vector<int> adj[mxN];

bool isBipartite(int u, int cu = 0){
    if(c[u] != -1){
        if(cu^c[u]){
            return false;
        }
        return true;
    }
    bool ok = 1;
    c[u] = cu;
    if(cu == 0){
        r++;
    }
    else if(cu == 1){
        b++;
    } 
    for(int v : adj[u]){
        ok &= isBipartite(v, cu^1);
    }
    return ok;
}

int main()
{
    ofstream fout("out");
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 0; i < n; i++){
            adj[i].clear();
        }
        for(int i = 0, a, b; i < m; i++){
            cin >> a >> b;
            adj[a].emplace_back(b);
            adj[b].emplace_back(a);
        }
        memset(c, -1, sizeof(c));
        bool ok = true;
        int cnt = 0;
        r = 0, b = 0;
        for(int i = 0; i < n; i++){
            if(c[i] < 0){
                r = 0, b = 0;
                ok &= isBipartite(i);
                cnt += max(1, min(r, b));
            }
        }
        if(!ok){
            cout << -1 << '\n';
        }else{
            cout << cnt << '\n'; 
        }
    } 
    return 0;
}