(UVA) 11080 - Place the Guards

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2021

用 "二分染色法" ， 用BFS實作(DFS也可XD)

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAX_N = 203;
const int MAX_M = 10004;

int visit[MAX_N];
vector<int> edg[MAX_N];
queue<int> que;

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            visit[x]=-1;
        }
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[j].push_back(i);
            edg[i].push_back(j);
        }
        int ans=0;
        for (int x=0;n>x;x++) {
            if (visit[x]==-1) {
                que.push(x);
                int _[2]={1,0};
                visit[x]=0;
                while (!que.empty()) {
                    int t=que.front();
                    que.pop();
                    for (auto i=edg[t].begin();i!=edg[t].end();i++) {
                        int tmp=*i;
                        if (visit[tmp]==-1) {
                            visit[tmp] = 1-visit[t];
                            _[visit[tmp]]++;
                            que.push(tmp);
                        }
                        else if (visit[tmp]==visit[t]) {
                            ans=-1;
                        }
                    }
                }
                if (ans==-1) continue;
                else if (_[1]==0) ans+=_[0];
                else ans+= min(_[0],_[1]);
            }
        }
        printf("%d\n",ans);
    }
}