#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 26 + 2;
int map[MAXN][MAXN];
int Color[MAXN];
int N;//number of repeaters
int MinColor;
string Str;//information about every repeater

void DFS(int Step, int CurColor)//Curlor record how many color exist when coming into step Step
{
	if(Step == N)
	{
		if(CurColor < MinColor)
			MinColor = CurColor;
		return;
	}
	if(CurColor >= MinColor)
		return;
	int flag = 0;
	for(Color[Step] = 1; Color[Step] <= CurColor; ++Color[Step])
	{
		int flag1 = 0;
		for(int i = 0; i < Step; ++i)
		{
			if(map[Step][i] && Color[Step] == Color[i])
			{
				flag1 = 1;
				break;
			}
		}
		if(!flag1)
			DFS(Step + 1, CurColor);
	}
	DFS(Step + 1, CurColor + 1);//无论是否可以用之前已经用过的颜色涂，都要用新的颜色涂一下，否则会出错
}

int main()
{
	while(cin >> N)
	{
		if(N == 0)
			break;
		cin.ignore();
		memset(map, 0, sizeof(map));
		memset(Color, -1, sizeof(Color));
		MinColor = 1000;
		for(int j = 1; j <= N; ++j)
		{
			getline(cin, Str);
			int row;
			int col;
			if(Str.length() > 2)
			{
				row = Str[0] - 'A';
				for(int i = 2; i < Str.length(); ++i)
				{
					col = Str[i] - 'A';
					map[row][col] = map[col][row] = 1;
				}
			}
		}
		Color[0] = 1;
		DFS(1, 1);
		if(MinColor == 1)
			cout << "1 channel needed." << endl;
		else
			cout << MinColor << " channels needed." << endl;
	}
	return 0;
}
/*
10
A:BCDEFG        
B:ACGH
C:ABDH
D:ACEHJ
E:ADFIJ
F:AEGI
G:ABFHI
H:BCDGIJ
I:EFGHJ
J:DEHI
*/

• 这个代码才是对的！顶起来 (12) yangyangc 2018-06-30 11:56:24