POJ1129 信道分配（DFS )

POJ1129 信道分配（DFS )

题目大意：每次有介于1-26个中继器，先输入一个数字n，表示中继器数量，然后一个冒号后面有与它相邻的中继器，每个中继器需要安排一个信道，不能与相邻的中继器相同，求最少的信道数量。

样本输入

2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0

示例输出

1 channel needed.
3 channels needed.
4 channels needed. 

思路简单，最多需要26个信道，从1开始dfs逐个尝试，成功分配到最后一个就返回

#include <cstdio>
#include <cstring>
bool neb[26][26];
int alo[26];
int n, ans, flag;
bool can;

void dfs(int deep){
	if(flag== n){
		can = true;
		return;
	}
	for(int i = 1;i <= ans;i++){
		int ok = 1;
		for(int j = 0;j < 26;j++){
			if(neb[deep][j] && alo[j] == i) ok = 0;
		}
		if(ok){
			alo[deep] = i;
			flag = deep + 1;
			dfs(deep + 1);
			if(flag == n) {
				can = true;
				return;
			}
			alo[deep] = 0;
		}
	}
}
int main() {
	while(scanf("%d", &n)){
		if(n == 0) break;
		memset(neb, false, sizeof(neb));
		memset(alo,0,sizeof(alo));
		char ch1, ch2;
		getchar();
		for(int i = 0;i < n;i++){
			ch1 = getchar();
			getchar();
			while((ch2 = getchar()) != '\n') {
				neb[ch1 - 'A'][ch2 - 'A'] = true;
			}
		}
		can = false;
		flag = 0;
		for(ans = 1;ans <= 26;ans++){
			dfs(0);
			if(can) break;
		}
		printf("%d %s needed.\n", ans, ans == 1 ? "channel" : "channels");
	}
	return 0;
}