图的m着色问题(回溯)
算法设计例题：图的m着色（回溯）
memory limit: 5000KB time limit: 2000MS
accept: 8 submit: 14
Description
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色，求有多少种方法为图可m着色。
Input
输入的第一个为测试样例的个数T （ T < 120 ），接下来有T个测试样例。每个测试样例的第一行是顶点数n、边数M和可用颜色数m（ n <= 10，M < 100，m <= 7 ），接下来M行，每行两个整数u和v，表示顶点u和v之间有一条边相连。（ 1 <= u < v <= n ）。
Output
对应每个测试样例输出两行，第一行格式为"Case #: W"，其中'#'表示第几个测试样例（从1开始计），W为可m着色方案数。
Sample Input
1
5 8 5
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
Sample Output
Case 1: 360
Author
Eapink
解决方法：
#include<iostream>
using namespace std;
#define N 100
int m,n,M,a[N][N],x[N],textNum;
int static sum=0;
bool ok(int k)
{
for(int j=1;j<=n;j++)
if(a[k][j]&&(x[j]==x[k]))
return false;
return true;
}
void backtrack(int t)
{
if(t>n)
{
sum++;
// for(int i=1;i<=n;i++)
//cout<<x[i]<<" ";
//cout<<endl;
}
else
for(int i=1;i<=m;i++)
{
x[t]=i;
if(ok(t))
backtrack(t+1);
x[t]=0;
}
}
int main()
{
int i,j,z=1;
cin>>textNum; //输入测试个数
while(textNum>0)
{
cin>>n; //输入顶点个数
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
cin>>M>>m; //输入边的个数、可用颜色数
for(int k=1;k<=M;k++) //生成图的邻接矩阵
{
cin>>i>>j;
a[i][j]=1;
a[j][i]=1;
}
/* for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;}*/
for(i=0;i<=n;i++)
x[i]=0;
backtrack(1);
cout<<"Case "<<z<<": "<<sum<<endl;
sum=0;
textNum--;
z++;
}
return 0;
}
补充：软件开发 , C++ ,
