图着色问题（回溯）

题目描述

给定无向连通图G=(V, E)，该图有n个顶点，e条边。用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。输出着色后的所有可能的结果。

输入

第一行三个整数，分别表示n，e 和 m 的值。1<=n,m<=10。
下面e行，每行二个整数，表示边的两个顶点，顶点编号为0,1,2,...,n-1。

输出

如果能用m种颜色着色，输出染色后的所有可能的结果（输出顺序见样例）；否则输出No solution。

样例输入 Copy

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

样例输出 Copy

1 2 1 3
1 3 1 2
2 1 2 3
2 3 2 1
3 1 3 2
3 2 3 1

#include<bits/stdc++.h>
using namespace std;
int n,e,m;
vector<vector<int>> G;
vector<int>col;
vector<vector<int>> res;
bool valid(int u,int c)
{for(int i=0;i<G[u].size();i++){if(col[G[u][i]]==c){return false;}}return true;
}
void solve(int u)
{if(u==n){res.push_back(col);return;}for(int c=1;c<=m;c++){if(valid(u,c)){col[u]=c;solve(u+1);col[u]=0;		}}	}
int main ()
{cin>>n>>e>>m;G.resize(n);col.resize(n,0);for(int i=0;i<e;i++){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}solve(0);if(res.empty()){cout<<"No solution"<<endl;}else{for(int i=0;i<res.size();i++){for(int j=0;j<n;j++){cout<<res[i][j]<<(j<n-1?" ":"\n");}}}return 0;
}
//by crtzk7