图的m着色问题

Description

给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色?

这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

编程计算：给定图G=(V, E)和m种不同的颜色，找出所有不同的着色法和着色总数。

Input

第一行是顶点的个数n（2≤n≤10），颜色数m（1≤m≤n）。

接下来是顶点之间的相互关系：a b

表示a和b相邻。当a，b同时为0时表示输入结束。

output

输出所有的着色方案，表示某个顶点涂某种颜色号，每个数字的后面有一个空格。最后一行是着色方案总数。

Sample Input

5 4
1 3
1 2
1 4
2 3
2 4
2 5
3 4
4 5
0 0

Sample Output

1 2 3 4 1 
1 2 3 4 3 
1 2 4 3 1 
1 2 4 3 4 
1 3 2 4 1 
1 3 2 4 2 
1 3 4 2 1 
1 3 4 2 4 
1 4 2 3 1 
1 4 2 3 2 
1 4 3 2 1 
1 4 3 2 3 
2 1 3 4 2 
2 1 3 4 3 
2 1 4 3 2 
2 1 4 3 4 
2 3 1 4 1 
2 3 1 4 2 
2 3 4 1 2 
2 3 4 1 4 
2 4 1 3 1 
2 4 1 3 2 
2 4 3 1 2 
2 4 3 1 3 
3 1 2 4 2 
3 1 2 4 3 
3 1 4 2 3 
3 1 4 2 4 
3 2 1 4 1 
3 2 1 4 3 
3 2 4 1 3 
3 2 4 1 4 
3 4 1 2 1 
3 4 1 2 3 
3 4 2 1 2 
3 4 2 1 3 
4 1 2 3 2 
4 1 2 3 4 
4 1 3 2 3 
4 1 3 2 4 
4 2 1 3 1 
4 2 1 3 4 
4 2 3 1 3 
4 2 3 1 4 
4 3 1 2 1 
4 3 1 2 4 
4 3 2 1 2 
4 3 2 1 4 
Total=48
Program ended with exit code: 0

代码

#include <iostream>

using namespace std;

int n,m;
int a=1,b=1;
int cou=0;
int graph[20][20]={0};
int color[20]={0};

bool ok(int c){
    for(int k=1;k<=n;k++){
        if(graph[c][k]&&color[c]==color[k]){
            return false;
        }
    }
    return true;
}

void backtrack(int cur){
    if(cur>n){
        for(int i=1;i<=n;i++){
            cout<<color[i]<<" ";
        }
        cou++;
        cout<<endl;
    }else{
        for(int i=1;i<=m;i++){
            color[cur]=i;
            if(ok(cur)){
                backtrack(cur+1);
            }
            color[cur]=0;
        }
    }
}

int main()
{
    cin>>n>>m;
    while((cin>>a>>b)&&a!=0&&b!=0){
        graph[a][b]=1;
        graph[b][a]=1;
    }
    backtrack(1);
    cout<<"Total="<<cou<<endl;
    return 0;
}