Posted on 2008-05-05 08:58
superman 阅读(357)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1084 C++ 00:00.01 836K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m;
7 bool map[26][26];
8
9 int x[26]; bool finded;
10
11 void search(int i)
12 {
13 if(finded)
14 return;
15 if(i > n)
16 {
17 finded = true;
18 return;
19 }
20 for(int col = 1; col <= m; col++)
21 {
22 x[i] = col;
23
24 int k;
25 for(k = 0; k < n; k++)
26 if(map[i][k] && x[i] == x[k])
27 break;
28 if(k == n)
29 search(i + 1);
30 }
31 }
32
33 int main()
34 {
35 freopen("p1084.in", "r", stdin);
36
37 while((cin >> n) && n)
38 {
39 memset(map, false, sizeof(map));
40
41 char s, t; getchar();
42 for(int i = 0; i < n; i++)
43 {
44 scanf("%c:", &s);
45 while((t = getchar()) != '\n')
46 map[s - 'A'][t - 'A'] = true;
47 }
48 for(m = 1; ; m++)
49 {
50 memset(x, 0, sizeof(x));
51 finded = false;
52 search(0);
53
54 if(finded)
55 {
56 cout << m << (m > 1 ? " channels " : " channel ") << "needed." << endl;
57 break;
58 }
59 }
60 }
61
62 return 0;
63 }
64