给定无向连通图G和m种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色。如果要求G的每条边的两个顶点着不同颜色。给出所有可能的着色方案；如果不存在，则回答“NO”。
利用回溯法。涂的时候从颜色1开始到m，每当涂上一个色，要判断第c个点是否可以涂这个色，不可以的话就不再往下涂了，改试另一个颜色，可以的话就继续。当c>n的时候即前n个点都涂完了，然后输出结果并cout++计数。
if(c>n){//如果涂的数目大于n，则表示已经成功涂完
输出color数组;
return;
}
for(int i=1;i<=m;i++){
color[c]=i;
if(点c可以涂){
draw(c+1);
}
color[c]=0;//回溯
}
有n个点，最坏情况下，每个点需要检查每一个子节点，复杂度为O(mn)，所以总的时间复杂度为O(nm^n)。
/*
author: keke
project name:图的m着色问题
Time Complexity: O(nm^n)
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int maxn = 1010;
int n, m, f, t, sum, color[maxn];
bool p[maxn][maxn];
bool jud(int x) {
for (int i = 1; i <= n; i++) {
if (p[x][i] && color[x] == color[i]) return false;
}
return true;
}
void draw(int x) {
if (x > n) {//如果涂色数目大于n，则表示已经完成全部涂色
for (int i = 1; i <= n; i++) cout << color[i] << (i == n ? "\n" : " ");
++sum;
return;
}
for (int i = 1; i <= m; i++) {
color[x] = i;
if (jud(x)) draw(x + 1);
color[x] = 0;//回溯
}
}
int main() {
ios::sync_with_stdio(false);
cout << fixed << setprecision(2);
cin >> n >> m;
while (cin >> f >> t) { //不断读取图的边，建图
if (f == 0 && t == 0) break;
p[f][t] = p[t][f] = true; //双向边
}
draw(1);
cout << "总共有" << sum << "种涂色方案" << "\n";
return 0;
// good job!
}
原文：https://www.cnblogs.com/powerkeke/p/12968666.html