下载文档原格式
图的m着⾊问题问题给定⽆向连通图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: kekeproject name:图的m着⾊问题Time Complexity: O(nm^n)*/#include <bits/stdc++.h>using namespace std;#define ll long long#define db doubleconst 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";return0; // good job! }。
