顶点着色的贪婪算法证明是存在的，即当前的算法得到只是给出最少颜色的一个上界。

算法描述：设G是一个图，它的顶点按某一顺序记为x1，x2,......xn.

(1) 对顶点x1指定颜色1。

(2)对每个i=2，3，....n,令p是在顶点x1,x2,...xi-1与xi相邻接的顶点中没有任何一个顶点着色p的最小的颜色，并且xi指定颜色p。

数学书上的定理为：设G是一个图，对于该图顶点的最大度为△，那么贪婪算法X产生G的顶点的一个（△+1）着色，因此 X（G）<=△+1

#include <cstdio>
#include <string>

int a[26][26], n, m, ans, c[26], b[26];
char s[26];

void greedy()
{
 int i, k;
 for(i = 0; i < n; i ++)
 {
  memset(b, 0, sizeof(b));
  for(k = 0; k < n; k ++)
  {
   if(a[i][k] && c[k] != -1)
   {
    b[c[k]] = 1;
   }
  }
  for(k = 0; k <= i; k ++)
  {
   if(!b[k]) break;
  }
  c[i] = k;
 }
 for(i = 0; i < n; i ++)
 {
  if(ans < c[i])
   ans = c[i];
 }
 ans ++;
}

void init()
{
 memset(a, 0, sizeof(a));
 for(int i = 0; i < n; i ++)
 {
  c[i] = -1;
 }
 ans = 0;
}

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) && n)
 {
  int i, k;
  init();
  for(i = 0; i < n; i ++)
  {
   scanf("%s", &s);
   m = strlen(s) - 2;
   for(k = 0; k < m; k ++)
   {
    a[i][s[k + 2] - 'A'] = 1;
    a[s[k + 2] - 'A'][i] = 1;
   }
  }
  greedy();
  if(ans != 1)
   printf("%d channels needed.\n", ans);
  else
   printf("%d channel needed.\n", ans);
 }
 return 0;
}

评论