#include<iostream> #include<cstdlib> #include<cstdio> using namespace std; int n,k,m,sum; int search(int); bool paint[50]; int pic[50][50],node[50]; bool pd(int,int); int main() { int x,y; scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); pic[x][y]=pic[y][x]=1;//相连 } search(1); printf("%d",sum); return 0; } int search(int x)//他的情况不是能涂哪个节点,因为我们就是从第一个开始涂色的,而是有m个颜色可涂; { if(x>n)sum++; else for(int i=1;i<=m;i++)//每一个有1-m种情况可以涂 { if(pd(x,i))//第x个涂第i种颜色 { node[x]=i;//第x个涂第i个颜色,这里记录的原因是为判断一个点和他相邻的点是否一个颜色 search(x+1); node[x]=0;//回溯 } } } bool pd(int x,int j)//判断 { for(int i=1;i<=n;i++) { if(pic[x][i]&&node[i]==j)//如果与它相连并且与它将要涂的颜色一样 return 0;//返回假 } return 1;//否则真 }
原文:http://www.cnblogs.com/zzyh/p/6623379.html