1 #include<cstdio> 2 #include<memory.h> 3 int n,num; 4 int d[100][100]; 5 int c[100]; 6  7 bool ok(int step) 8 { 9     for(int i = 0; i < n; i++)10         if(d[step][i] == 1 && c[step] == c[i]) return false;11     return true;12 }13 14 bool dfs(int num,int step)15 {16     if(step >= n) return true;17     for(int i = 1; i <= num; i++)18     {19         c[step] = i;20         if(ok(step) && dfs(num,step+1)) return true;21 22         c[step] = 0;//恢复23     }24     return false;25 }26 27 int main()28 {29     freopen("input.txt","r",stdin);30     while(scanf("%d\n",&n) && n)31     {32         char ch;33         memset(d,0,sizeof(d));34         for(int i = 0; i < n; i++)35         {36             scanf("%c:",&ch);37             while(scanf("%c",&ch) && ch != ‘\n‘)38                 d[i][ch - ‘A‘] = d[ch - ‘A‘][i] = 1;39         }40 41         memset(c,0,sizeof(c));42         int num = 0;43         for(num = 1; num < 4; num++)44             if(dfs(num,0)) break;45 46         if(num == 1) printf("1 channel needed.\n");47         else printf("%d channels needed.\n",num);48 49     }50     return 0;51 }