问题 C: 【回溯】图的m着色问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版]
题目描述
给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色?
这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
编程计算：给定图G=(V, E)和m种不同的颜色，找出所有不同的着色法和着色总数。
输入
第一行是顶点的个数n（2≤n≤10），颜色数m（1≤m≤n）。
接下来是顶点之间的相互关系：a b
表示a和b相邻。当a，b同时为0时表示输入结束。
输出
输出所有的着色方案，表示某个顶点涂某种颜色号，每个数字的后面有一个空格。最后一行是着色方案总数。
样例输入
5 4
1 3
1 2
1 4
2 3
2 4
2 5
3 4
4 5
0 0
样例输出
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
解题思路：使用回溯法，具体步骤是将cur=1传入backtrack（），即从第一个开始涂色。
涂的时候从颜色1开始到m，每当涂上一个色，要用ok（cur）判断第cur个点是否可以涂这个色，不可以的话就不再往下涂了，改试另一个颜色，可以的话就继续。
当cur>n的时候即前n个点都涂完了，然后输出结果并cou++计数。
代码：
#include <iostream>
#include <cstdio> using namespace std; int n,m;
int a=,b=;
int cou=;
int graph[][]={};
int color[]={}; bool ok(int c){
for(int k=;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=;i<=n;i++){
printf("%d ",color[i]);
}
cou++;
printf("\n");
}else{
for(int i=;i<=m;i++){
color[cur]=i;
if(ok(cur)){
backtrack(cur+);
}
color[cur]=;
}
}
} int main()
{
scanf("%d %d",&n,&m);
while(scanf("%d %d",&a,&b)!=EOF&&a!=&&b!=){
graph[a][b]=;
graph[b][a]=;
}
backtrack();
printf("Total=%d",cou);
return ;
}