図のシェーディングの問題

アルゴリズムの分類:
さかのぼる
アルゴリズムの原理:
『アルゴリズム設計技術と分析』P 219参照
アルゴリズム時間の複雑さ:
最悪時間複雑度(n 3^n)
コード実装:(POJ 1129)

/* Author: jokes000
 * POJ 1129
 * Channel Allocation
 */

#include <iostream>
#include <string.h>
using namespace std;

int G[27][27];	//         
int C[27];		//           
int n;			//        
bool flag;		//         

//       
// pos:       
// maxcolor:     
void color(int pos, int maxcolor) {
	
	for (int c = 1; c <= maxcolor; ++ c) {
		C[pos] = c;
		bool legal = true;
		//         
		for (int i = 1; i <= n; ++ i) {
			if (G[pos][i] == 1) {
				if (C[pos] == C[i]) {
					legal = false;
					break;
				}
			}
		}

		if (legal) {
			if (pos == n) {
				flag = true;
				return;
			} else {
				color(pos+1, maxcolor);
			}
		}
	}
};

void solve() {
	flag = false;
	int  maxcolor = 0;

	while (!flag) {
		++ maxcolor;
		color(1, maxcolor);
	}

	if (maxcolor == 1)
		printf("%d channel needed.
",maxcolor);
	else
		printf("%d channels needed.
",maxcolor);
};

int Convert(char s) {
	return s - 'A' + 1;
}

void init() {
	char in[30];

	memset(G, 0, sizeof(G));
	memset(C, 0, sizeof(C));

	for (int i = 0; i < n; ++ i) {
		scanf("%s",in);
		int s = Convert(in[0]);
		int len = strlen(in);
		for (int j = 2; j < len; ++ j) {
			int e = Convert(in[j]);
			G[s][e] = G[e][s] = 1;
		}
	}
};

int main() {

	while (scanf("%d",&n)!=EOF, n) {
		init();
		solve();
	}
}