前些日子看了下“湖南省第二屆大學生程序設計大賽”的一些題目，看到第三題的時候，沒點什么思路，后來想了想像是圖頂點著色的問題。
又重新拾起了《離散數(shù)學》（哎呀，大一時候，沒學好呀）書上介紹了 Welch Powell的方法進行著色。
算法大致如下：
1.把圖中的頂點按度數(shù)減小的次序排列
2.用第一種顏色對第一點著色，并且按排列次序，對前面著色點不相鄰的每一點著上同樣的顏色
3.把第二種顏色對尚未著色的點重復（2），用第三種顏色繼續(xù)，直到所有點全部上色為止
用c++實現(xiàn)如下:
#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)//與已經(jīng)涂的點相連
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;
}