Fotolog

A través del espejo
2010-10-12: A través del espejo
¡La radio habla en binario!
2010-10-10: ¡La radio habla en binario!
Gigaminx (regalo por mi cumple)
2010-09-16: Gigaminx (regalo por mi cumple)
Trini en bici
2010-09-05: Trini en bici
Valporquero
2010-08-28: Valporquero
Mi bici nueva
2010-08-22: Mi bici nueva
Boda de Mario y Ana
2010-08-13: Boda de Mario y Ana
De cañones en Guara
2010-08-07: De cañones en Guara
Trini y Mari en Marbella
2010-08-05: Trini y Mari en Marbella
Trini y Chelo en Tabarca
2010-08-03: Trini y Chelo en Tabarca
Valid XHTML 1.1
Acceder
Volver a la lista de problemas

Bicoloring

10004.c

#include <stdio.h>
#include <string.h>

int n,l;
int arr[205][205];
int col[205];

void
colorea(void) {
	int i,j;

	while (1) {
		int done = 1;
		for (i=0; i<n; i++) {
			if (col[i] == 0) {
				done=0;
			}
			if (col[i] != 0) {
				for (j=0; j<n; j++) {
					if (arr[i][j]) {
						if (!col[j]) {
							col[j] = (col[i] ^ 1);
						}
						if (col[j] != (col[i] ^ 1)) {
							printf("NOT BICOLORABLE.\n");
							return;
						}
					}
				}
			}
		}
		if (done) {
			printf("BICOLORABLE.\n");
			return;
		}
	}
}

int
main(void) {
	int a,b;
	int i;

	while (1) {
		scanf("%d %d", &n, &l);
		if (n==0) {
			return 0;
		}
		memset(arr, 0, sizeof(arr));
		memset(col, 0, sizeof(col));
		for (i=0; i<l; i++) {
			scanf("%d %d", &a, &b);
			arr[a][b] = arr[b][a] = 1;
		}
		col[0] = 2;
		colorea();
	}
}