Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Graph Coloring

193.c

#include <stdio.h>

#define VACIO 0
#define NEGRO 1		/* El resto: blanco */

int num_nodes;
int nodes[100];
int conn[100][100];	/* 1 if nodes i and j are connected */

int best_nodes[100];
int max_negros=0;

void
calc(int nodenum, int negros)
{
	int i;
	int all_done=0;

	nodes[nodenum]=NEGRO;
	negros++;

	if (negros>max_negros) {
		max_negros=negros;
		all_done=1;
	}

	for(i=0; i<num_nodes; i++) {
		if (conn[nodenum][i] && nodes[i]==VACIO) {
			nodes[i]=10+nodenum;	/* BLANCO */
		}
	}
	for(i=0; i<num_nodes; i++) {
		if (nodes[i]==VACIO) {
			calc(i,negros);
			all_done=0;
			break;
		}
	}
	if (all_done) {
		memcpy(best_nodes, nodes, sizeof(nodes));
	}
	for(i=0; i<num_nodes; i++) {
		if (nodes[i]==10+nodenum) {
			nodes[i]=VACIO;
		}
	}
	nodes[nodenum]=10+nodenum;	/* BLANCO */
	negros--;
	for(i=0; i<num_nodes; i++) {
		if (nodes[i]==VACIO) {
			calc(i,negros);
			break;
		}
	}
	nodes[nodenum]=VACIO;
}

int
main(void)
{
	int i,j,k;
	int n,m;
	int a,b;

	scanf("%d", &n);
	for(i=0; i<n; i++) {
		scanf(" %d %d", &num_nodes, &m);
		max_negros=0;
		for(j=0; j<num_nodes; j++) {
			nodes[j]=0;
			for(k=0; k<num_nodes; k++) {
				conn[j][k]=0;
			}
		}
		for(j=0; j<m; j++) {
			scanf(" %d %d", &a, &b);
			conn[a-1][b-1]=1;
			conn[b-1][a-1]=1;
		}
		calc(0,0);
		printf("%d\n", max_negros);
		a=0;
		for(j=0; j<num_nodes; j++) {
			if (best_nodes[j]==NEGRO) {
				printf("%s%d", (a ? " " : ""), j+1);
				a=1;
			}
		}
		printf("\n");
	}
	exit(0);
}