uva - 193 Graph Coloring(回溯）

题意：给你一个图形，你的任务是找到一种最佳涂色的方法。图形中的点要被涂顏色（只能涂黑色或白色），而且任何2个相连的点不可以都涂黑色。所谓最佳的涂色方法是指让这个图形黑色的点最多。以下图形的涂色即是一种最佳涂色。

方法：回溯，枚举所有点的黑白情况，然后判断可行性。

参考：http://blog.csdn.net/goomaple/article/details/7957258

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAX 100+10

int G[MAX][MAX], color[MAX], ans[MAX];
int n, k, _max;

void Creat_Graph()
{
	int i = 0, a = 0, b = 0;
	cin >> n >> k;
	for (i = 0; i < k; i++)
	{
		cin >> a >> b;
		G[a][b] = 1, G[b][a] = 1;
	}
}

int judge(int cur)
{
	for (int i = 1; i <= n; i++)
	{
		if (G[i][cur] && color[i])
			return 0;
	}
	return 1;
}

void dfs(int cur)
{
	int i = 0, j = 0;
	if (cur > n)
	{
		int count = 0;
		for(i = 1; i <= n; i++)
			if (color[i])
				count++;
		if (count > _max)
		{
			_max = count;
			for (i = 1, j = 0; i <= n; i++)
				if (color[i])
					ans[j++] = i;
		}
		return;
	}
	else
	{
		color[cur] = 0;
		dfs(cur+1);
		color[cur] = 1;
		if (judge(cur))
			dfs(cur+1);
		color[cur] = 0;
	}
}

int main()
{
#ifdef Local
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int t = 0, i = 0;
	cin >> t;
	while (t--)
	{
		memset(G, 0, sizeof(G));
		memset(color, 0, sizeof(color));
		memset(ans, 0, sizeof(ans));
		_max = 0;
		Creat_Graph();
		dfs(1);
		cout << _max << endl;
		for (i = 0; i < _max; i++)
		{
			if (i != _max - 1)
				cout << ans[i] << ‘ ‘;
			else
				cout << ans[i];
		}
		cout << endl;
	}
}

uva - 193 Graph Coloring(回溯）

原文：http://blog.csdn.net/u013545222/article/details/18922591