pku1129 Channel Allocation

#include<stdio.h>

const int Maxn=26;
bool g[Maxn][Maxn];
int x[Maxn];
int n;

bool match(int pos)
{
    for(int i=0;i<pos;i++)
        if(g[pos][i]&&(x[pos]==x[i]))
            return false;
    return true;
}

void solve(int k)
{
    for(int i=0;i<n;i++)
        x[i]=0;

    int pos=0;
    while(pos>=0)
    {
        x[pos]++;
        while(x[pos]<=k&&!match(pos))
            x[pos]++;
        if(x[pos]<=k)
        {
            if(pos==n-1)    
                break;
            else
                pos++;
        }
        else
        {
            x[pos]=0;
            pos--;
        }
    }
}

int main()
{
    while(scanf("%d",&n),n)
    {
        getchar();
        char c;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                g[i][j]=false;
        for(int i=0;i<n;i++)
        {
            getchar();getchar();
            while((c=getchar())!='\n')
            {
                g[i][c-'A']=true;
            }
        }

        int k=0;
        do
        {
            k++;
            solve(k);
        }while(x[0]==0);

        if(k==1)
            printf("1 channel needed.\n");
        else
            printf("%d channels needed.\n",k);
    }
    return 0;
}