問題起源於一個宣講會時間安排問題，有若干個部門要進行宣講會，有若干個同學對多個部門有興趣，希望在給出一個時間方案，要求所有的同學都可以參加所有他感興趣的宣講會，同時要求在最短的時間內把宣講會結束。
把每個宣講會作為一個點，每個同學感興趣的宣講會兩兩相連，就變成了一個圖的最少著色問題。
而圖的著色問題可以在多項式時間內完成（為什麼有的書上說沒有多項式算法？感覺很奇怪，明明可以做到），圖的顏色編號，也就是宣講會的宣講時間編號，其中最大的顏色編號也就是所需要的最長時間 。
算法思想： 深度遍歷，遍歷過程中設置頂點的顏色，設定規則是: 查找所有相鄰的頂點，選擇一個未被使用過的編號最小的顏色，把這個顏色作為當前節點顏色。
算法正確性： 算法執行過程，保證了每個頂點都與其他相鄰頂點顏色不同，同時又保證了使用最少的顏色數目，顯然是正確的。
#include <iostream>
#define Max 15
using namespace std;
int vertexCount=0;
int color[Max]={0};
int arc[Max][Max]={0};
int visited[Max]={0};
void init()
{
cout<<"請輸入定點數目：\n";
cin>>vertexCount;
int t;
cout<<"請輸入邊的數目：\n";
cin>>t;
for(int i=0;i!=t;++i)
{
cout<<"請輸入第"<<i+1<<"條邊：\n";
int a,b;
cin>>a>>b;
arc[a-1][b-1]=1;
arc[b-1][a-1]=1;
}
}
void DFSTraverse(int s)
{
if(visited[s]) return;
int t=1;
bool flag;
do{
flag=false;
for(int i=0;i!=vertexCount;++i)
{
if(arc[s][i]&&color[i]==t)
{
flag=true;
t++;
break;
}
}
}while(flag);
color[s]=t;
visited[s]=1;
for(int i=0;i!=vertexCount;++i)
{
if(arc[s][i]&&visited[i]==0)
DFSTraverse(i);
}
}
void show()
{
for(int i=0;i!=vertexCount;++i)
cout<<"頂點"<<i+1<<" 顏色"<<color[i]<<endl;
}
void main()
{
init();
for(int i=0;i!=vertexCount;++i)
DFSTraverse(i);
show();
::system("pause");
}
