前些日子看了下“湖南省第二届大学生程序设计大赛”的一些题目，看到第三题的时候，没点什么思路，后来想了想像是图顶点着色的问题。
又重新拾起了《离散数学》（哎呀，大一时候，没学好呀）书上介绍了 Welch Powell的方法进行着色。
算法大致如下：
1.把图中的顶点按度数减小的次序排列
2.用第一种颜色对第一点着色，并且按排列次序，对前面着色点不相邻的每一点着上同样的颜色
3.把第二种颜色对尚未着色的点重复（2），用第三种颜色继续，直到所有点全部上色为止
用c++实现如下:
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n;
int color[100];// 顶点i涂得颜色
int col_kinds;
int link[100][100];
class Nodes
{
public:
int degree;
int index;
bool operator>(const Nodes &n)
{
return degree>n.degree;
}
};
bool cmp(const Nodes &m,const Nodes &n)
{
return m.degree>n.degree;
}
Nodes p[100];
bool Check_ok(int i,int j)
{
int k;
if(link[p[i].index][p[j].index]!=0||color[j]!=0) return false;//相连的情况
for(k=0;k<j;k++)
{
if(link[p[i].index][p[k].index]==0&&link[p[k].index][p[j].index]!=0)//与已经涂的点相连
return false;
}
return true;
}
void Welech_Powell()
{
int i,j;
for(i=0;i<n;i++)
{
if(color[i]==0)
{
color[i]=++col_kinds;
for(j=0;j<n;j++)
{
if(Check_ok(i,j))
{
color[j]=col_kinds;
}
}
}
}
}
int main()
{
int i,j,e,k;
ifstream fin("input.txt");
while(fin>>n>>e)
{
col_kinds=0;
memset(link,0,sizeof(link));
memset(color,0,sizeof(color));
for(k=0;k<e;k++)
{
fin>>i>>j;
link[i][j]=link[j][i]=1;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<link[i][j]<<" ";
cout<<endl;
}
//--
for(i=0;i<n;i++)
{
p[i].index=i;
p[i].degree=0;
for(j=0;j<n;j++)
p[i].degree+=link[i][j];
}
sort(p,p+n,cmp);
Welech_Powell();
cout<<col_kinds<<endl;
for(i=0;i<n;i++)
cout<<p[i].index<<" "<<color[i]<<" "<<endl;
}
return 0;
}