Saturday, June 13, 2015

UVa 10004 - Bicoloring

// 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;
}

No comments:

Post a Comment