2012年11月26日

UVa 10004 - Bicoloring


#include <cstdio>
#include <vector>

std::vector<int> v[210];
int flag, rec[210];

void dfs(int now, int c) {
  if (!flag) return;
  rec[now] = c;
  for (int i = 0; i < v[now].size(); i++)
    if (rec[v[now][i]] == -1) dfs(v[now][i], !c);
    else if (rec[v[now][i]] == c) flag = 0;
}

int main() {
  int n, m, c = 1;
  while (scanf("%d", &n) && n) {
    int a, b;
    for (a = 0; a <= n; a++) {
      v[a].clear();
      rec[a] = -1;
    }
    scanf("%d", &m);
    while (m--) {
      scanf("%d%d", &a, &b);
      v[a].push_back(b);
      v[b].push_back(a);
    }
    flag = 1;
    dfs(0, 0);
    if (flag) puts("BICOLORABLE.");
    else puts("NOT BICOLORABLE.");
  }
  return 0;
} 

沒有留言:

張貼留言