图的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++ ,