(UVA) 10004 - Bicoloring

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

BFS一番即可XD

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

const int MAX_N = 203;

int w[MAX_N][MAX_N];
int col[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        int m;
        scanf("%d",&m);
        memset(w,0,sizeof(w));
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            w[i][j] = w[j][i] = 1;
        }
        queue<int> que;
        que.push(0);
        memset(col,-1,sizeof(col));
        bool ans=true;
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (int x=0;n>x;x++) {
                if (w[t][x]==1 && col[x]==-1) {
                    col[x] = 1-col[t];
                    que.push(x);
                }
                else if (w[t][x]==1 && col[x]==col[t]) ans=false;
            }
        }
        printf("%s\n",ans?"BICOLORABLE.":"NOT BICOLORABLE.");
    }
}