// UVa 10004 - Bicoloring #include <iostream> #include <string.h> using namespace std; int lnk[200][200], c[200], C[200]; bool paint(int node, int color) { C[node] = color; for (int i = 0; i < c[node]; i++) { if (C[lnk[node][i]] == color) return false; else if (C[lnk[node][i]] == 0) { if (!paint(lnk[node][i], color == 1 ? 2 : 1)) return false; } } return true; } int main() { int m, n; while (cin >> n >> m) { memset(c, 0, sizeof(c)); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; lnk[a][c[a]++] = b; lnk[b][c[b]++] = a; } memset(C, 0, sizeof(C)); bool bi = paint(0, 1); cout << (bi ? "BICOLORABLE." : "NOT BICOLORABLE.") << endl; } return 0; }
Saturday, June 13, 2015
UVa 10004 - Bicoloring
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment