图的着色

#include<stdio.h>
#include<string.h>
const int MN=30;

int mat[MN][MN],opt[MN];
char s[MN];
int n;
//判断相邻的顶点的颜色是否相同
bool same(int cur)
{
    for(int i=0;i<n;i++)
    {
        if(mat[i][cur] && opt[cur]==opt[i]) return true;
    }
    return false;
}

bool DFS(int cur,int Maxcolor)
{
    if(cur==n) return true;
    for(opt[cur]=1;opt[cur]<=Maxcolor;opt[cur]++)//枚举颜色
    {//若相邻的颜色没有一样的，继续往下搜
        if(!same(cur)) return DFS(cur+1,Maxcolor);
    }
    return false;
}

int main()
{
    int i,j;
    while(scanf("%d",&n) && n)
    {
        memset(mat,0,sizeof(mat));
        memset(opt,0,sizeof(opt));
        getchar();
        for(i=1;i<=n;i++)
        {
            gets(s);
            int x=s[0]-'A';
            for(j=2;s[j];j++)
            {
                int y=s[j]-'A';
                mat[x][y]=mat[y][x]=1;
            }
        }
        for(i=1;i<=4;i++)
        {
            if(DFS(0,i)) break;
        }
        if(i==1) printf("1 channel needed.\n");
        else printf("%d channels needed.\n",i);
    }
    return 0;
}