Channel Allocation
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <string>
7 #include <vector>
8 #include <set>
9 #include <map>
10 #include <stack>
11 #include <queue>
12 #include <sstream>
13 #include <iomanip>
14 using namespace std;
15 typedef long long LL;
16 const int INF = 0x4fffffff;
17 const double EXP = 1e-5;
18 const int MS = 28;
19 const int SIZE = 100005;
20
21
22 int edges[MS][MS];
23 char str[MS];
24 int used[MS];
25 int color[MS];
26 int ans,n;
27
28 void greedy()
29 {
30 for(int i=0;i<n;i++)
31 {
32 memset(used,0,sizeof(used));
33 for(int j=0;j<n;j++)
34 {
35 if(edges[i][j]&&color[j]!=-1)
36 used[color[j]]=1;
37 }
38 int k;
39 for(k=0;k<i;k++)
40 {
41 if(!used[k])
42 break;
43 }
44 color[i]=k;
45 }
46 ans=0;
47 for(int i=0;i<n;i++)
48 if(ans<color[i])
49 ans=color[i];
50 ans++;
51 }
52
53
54 int main()
55 {
56 while(scanf("%d",&n)&&n)
57 {
58 memset(color,0xff,sizeof(color));
59 memset(edges,0,sizeof(edges));
60 for(int i=0;i<n;i++)
61 {
62 scanf("%s",str);
63 int len=strlen(str);
64 for(int j=2;j<len;j++)
65 edges[i][str[j]-'A']=edges[str[j]-'A'][i]=1;
66 }
67 greedy();
68 if(ans==1) // 注意单复数
69 printf("%d channel needed.
",ans);
70 else
71 printf("%d channels needed.
",ans);
72 }
73 return 0;
74 }