图着色问题（回溯）

题目描述

给定无向连通图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