题目背景

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

样例输入 #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。

题目分析

由于题中数据较小，所以我们可以直接用深搜暴力搜索各个节点。
题目给出了图中的各个线段，要求在各个节点上涂色，使得一条线段的两个节点颜色不同，并输出总方案数。
我们可以定义一个布尔数组a来存储两个节点间是否有线段。
并定义一个数组color存储节点的颜色。
涂色的过程可以用for循环，用i代表颜色，一直++直到m。同时还要特判一下一条线段的顶点是否涂了同一颜色。 当x大于n时，说明所有节点都搜索了一遍，则sum++。

AC代码

#include<bits/stdc++.h>
using namespace std;
<p>void search(int);
int check(int,int);</p>
<p>int n,k,m;  //n个顶点,k条边，m种颜色
int a[200][200]={0},b[200]={0},sum=0;
//sum用来存储方案数，a记录结点路径，b用于记录已染色的点</p>
<p>int main(){</p>
<pre><code>int t1,t2;
cin&gt;&gt;n&gt;&gt;k&gt;&gt;m;
for(int i=1;i&lt;=k;i++){
    cin&gt;&gt;t1&gt;&gt;t2;
    a[t1][t2]=1; //无向图,双方可到达
    a[t2][t1]=1;
}
search(1); //从1找起
cout&lt;&lt;sum;

return 0;

} void search(int x){

if(x&gt;n){
	sum++; //若x&gt;n则已染色完成，方案+1
	return;
}  
for(int i=1;i&lt;=m;i++){ //枚举颜色 
    if(b[x]==0&amp;&amp;check(i,x)==1){  //若改点未染色，且该点相邻点中无同色点
	  	b[x]=i;        //标记已染色
        search(x+1);   //染下一个点
        b[x]=0;        //还原标记
    }
}

} int check(int x,int y){

for(int i=1;i&lt;=n;i++){  //寻找相邻点
    if(i==y){
		continue;  //肯定不能比较自己与自己是否相同啦，跳过
	}  
    if(a[y][i]==1&amp;&amp;b[i]==x){
		return 0; //若y点可到达i点，且两者颜色相同，返回0
	}
}
return 1;  //符合条件可以染色，返回1

}

AC链接原题链接