P2819 图的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 41 21 31 42 32 42 53 44 5

输出样例#1：

48

说明

n<=100;k<=2500;

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

保证答案不超过20000。

 

#include
     
      #include
      
       #include
       
        #include
        
         #define N 500using namespace std;int n,m,k,x,y,ans,col[N],a[N][N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int pd(int x,int y){    for(int i=1;i<=n;i++)    {        if(i==x) continue;        if(y==col[i]&&a[x][i]) return false;      }      return true;}void dfs(int x){    if(x>n){ans++; return ;}    for(int i=1;i<=k;i++)    {        if(!col[x]&&pd(x,i))        {            col[x]=i;            dfs(x+1);            col[x]=0;         }     }}int main(){    n=read(),m=read(),k=read();    for(int i=1;i<=m;i++)     x=read(),y=read(),a[x][y]=a[y][x]=1;    dfs(1);    printf("%d",ans);    return 0;}