UVa 193 Graph Coloring

題意：
    黑色不能相鄰，白色則不限制，如果編號最大的點是黑色的，則稱這個填入方法為optimal。題目給定一個graph，求填入最多黑色的方法，如果有多個答案，則盡可能選擇optimal的那種。

想法：
    MaxNum為填入最多黑色的點的數量，透過backtracking找出多種填入的方式，並不斷刷新MaxNum，並將該填法記錄下來，最後輸出最大MaxNum的填入方式，詳細見底下code。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int M, N, K;
	vector<int> toNxt[105];
	int color[105]; // Black is 1, White is 2
	int MaxNum;
	vector<int> Container, Ans;
	void Initial(int N);
	void backtracking(int n);
	int main()
	{
	scanf("%d", &M);
	while (M--) {
	scanf("%d %d", &N, &K);
	Initial(N);
	int a, b;
	for (int i = 0; i < K; ++i) {
	scanf("%d %d", &a, &b);
	toNxt[a].push_back(b);
	toNxt[b].push_back(a);
	}
	backtracking(1); //從1開始填到N
	printf("%d\n%d", MaxNum, Ans[0]);
	for (int i = 1; i < MaxNum; ++i)
	printf(" %d", Ans[i]);
	putchar('\n');
	}
	}
	void Initial(int N)
	{
	Container.clear();
	MaxNum = 0;
	for (int i = 1; i <= N; ++i) {
	toNxt[i].clear();
	color[i] = 0;
	}
	}
	void backtracking(int n)
	{
	if (n > N) {
	//如果這個填法黑色數量比MaxNum大或是等於MaxNum但最後一個是黑色,則更新MaxNum和Ans
	if (Container.size() > MaxNum ||
	Container.size() == MaxNum && color[n - 1] == 1) {
	MaxNum = Container.size();
	Ans = Container;
	}
	return;
	}
	bool hasBlack = true; //確認這個node能不能填入黑色
	for (int i : toNxt[n])
	if (color[i] == 1) hasBlack = false;
	if (hasBlack) {
	Container.push_back(n);
	color[n] = 1;
	backtracking(n + 1);
	Container.pop_back();
	color[n] = 0;
	}
	color[n] = 2;
	backtracking(n + 1);
	color[n] = 0;
	}

view raw [UVa] 193 Graph Coloring.cpp hosted with ❤ by GitHub