m图的着色问题

题目背景

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

题目描述

对于给定的无向连通图G和m种不同的颜色，编程计算图的所有不同的着色法。

输入格式

第1行有3个正整数n，k 和m，表示给定的图G有n个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。

输出格式

程序运行结束时，将计算出的不同的着色方案数输出。

输入输出样例

输入 #1

5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

输出 #1

48

说明/提示

n<=100;k<=2500;

在n很大时保证k足够大。

保证答案不超过20000。

笔记：搜索是按一定规律有序进行的，然后再一步一步得退回来，切记一顿子乱搜

邻接矩阵实现：

#include<bits/stdc++.h>
using namespace std;
int n,k,m,ans;
int mp[105][105];
int color[105];
int tt[100];
bool check(int x,int t){
	for(int i=1;i<x;i++){
		if(mp[x][i]==1&&t==color[i])return false;
	}
	return true;
}
void dfs(int sum){
	if(sum>n){
		ans++;
		return;
	}
	for(int i=1;i<=m;i++){
		if(check(sum,i)){
			color[sum]=i;
			dfs(sum+1);
			color[sum]=0;
		}
	}
}
int main(){
	cin>>n>>k>>m;
	//邻接矩阵 
	for(int i=0;i<k;i++){
		int x,y;
		cin>>x>>y;
		mp[x][y]=1;
		mp[y][x]=1;
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

邻接表实现：

#include<bits/stdc++.h>
using namespace std;
int n,k,m,ans;
int color[1005];
vector<int> mp[100];
bool check(int x,int p){
	for(int i=0;i<mp[x].size();i++){
		if(color[mp[x][i]]==p)return false; 
	}
	return true;
}
void dfs(int dot){
	if(dot>n){
		ans++;
		return;
	} 
	for(int i=1;i<=m;i++){
		if(check(dot,i)){
			color[dot]=i;
			dfs(dot+1);
			color[dot]=0; 
		}
	} 
}
int main(){
	cin>>n>>k>>m;
	//邻接表 
	for(int i=0;i<k;i++){
		int x,y;
		cin>>x>>y;
		mp[x].push_back(y);
		mp[y].push_back(x); 
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}