Title Link: https://cn.vjudge.net/contest/311091#problem/L
Sample Input

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

Sample Output

1 channel needed.
3 channels needed.
4 channels needed

Analysis: broadcast station needs repeaters, each repeater needs A good choice of channels, and the adjacent repeaters must use different channels. How many channels do you need at least? N repeaters, the first line adjacent to A, the second line connected to B, and so on...

Analysis: repeater is equivalent to point, channel is equivalent to color. Adjacent points cannot be painted with the same color. How many colors are needed at least?

Graph coloring problem solving algorithm: approximate efficient algorithm - sequential coloring algorithm (closely related to the coloring order of points)
(1) i is the vertex number, i=1;
(2) c is used to color vertex i as the c color, c=1;
(3) for coloring the ith vertex, consider whether the adjacent vertices have been shaded. If not, use the C color, and turn to the next vertex. If the adjacent vertices have used C color, then c + +, then judge.
Note: the worst case is i vertex, i colors are used. The purpose of this algorithm is to make the number of colors used by i vertex less than i under the premise of satisfying the conditions.

Code:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int c[100];  //The number of vertex coloring and the color of each vertex
int n,book[100],e[100][100],sum;
void solve(){
    int u;
    for(int i=0; i<n; i++){
        memset(book,0,sizeof(book));
        for(int j=0; j<n; j++)//Determine whether adjacent vertices use color
        {
            if(e[i][j]&&c[j]!=-1)
                book[c[j]]=1;
        }
        for(int k=0; k<=i; k++) //For the ith vertex, you need at most i colors
        {
            if(book[k]==0)
            {
                u=k;
                break;
            }
        }
        c[i]=u;//Use the u color for the i th vertex
    }
    for(int i=0; i<n; i++)//The algorithm gets the minimum color, so it needs to find the maximum value.
    {
        if(sum<c[i])
            sum=c[i];
    }
    sum++;
}
int main(){
    char a[100];
    while(~scanf("%d",&n)&&n){
        sum=0;
        memset(c,-1,sizeof(c));
        memset(e,0,sizeof(e));
        for(int i=0; i<n; i++){
            scanf("%s",a);
            for(int j=2; j<strlen(a); j++)
                e[i][a[j]-'A']=1;//Two points adjacent
        }
        solve();
        if(sum==1)
            printf("%d channel needed.\n",sum);
        else
            printf("%d channels needed.\n",sum);
    }
    return 0;
}

Character is based on willpower. Only when self-discipline and creative potential are shaped, can we have the ability to move and make noise outside our hearts. Self discipline is the willpower of the needle.