着色问题

题目描述
给定无向连通图G 和M 种不同的颜色，用这些颜色为图G 的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G 中每条边的2 个顶点着不同的颜色，则称这个图是M 可着色的。图的M 着色问题是对于给定图G 和M 种颜色，找出所有不同的着色法。
对于给定的无向连通图G 和M 种不同的颜色，编程计算图的所有不同的着色法。

输入
第一行有3 个正整数N，K 和M，表示给定的图G 有N 个顶点和K 条边，M 种颜色。顶点编号为1，2……，N。接下来的K 行中，每行有2 个正整数U，V，表示图G 的一条边（U，V）。
数据范围：1<N<=100 1<K<=2500 1<M<=6

输出
不同的着色方案数

样例输入
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

样例输出
48

这虽然是一道搜索题，但思路和写法上都和我以前写的不太一样，算是长知识了。

首先开了一个这么个数组，a[i][j] 代表和点 i 相邻的点中是第 j 号颜色的点有多少个。所以只有当 a[i][j] == 0时，点 i 才能被染成第 j 号颜色。

然后对于每一个点，枚举所有颜色，当颜色 j 符合条件时就染色。那么如何表示 i 这个点被染成第 j 号颜色呢？那就是把和 i 相连的所有点k a[k][j]++。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 const int maxn = 1e4 + 5;
11 int n, k, m, tot[maxn][10];
12 vector<int>v[maxn];
13 int ans = 0;
14 void dfs(int step)
15 {
16     if(step == n + 1) {ans++; return;}
17     for(int i = 1; i <= m; ++i)
18     {
19         if(!tot[step][i])
20         {
21             for(int j = 0; j < v[step].size(); ++j) tot[v[step][j]][i]++;        //染色 
22             dfs(step + 1);
23             for(int j = 0; j < v[step].size(); ++j) tot[v[step][j]][i]--;        //回溯 
24         }
25     }
26 }
27 int main() {
28   freopen("color.in", " r", stdin);
29   freopen("color.out", "w", stdout);
30     scanf("%d%d%d", &n, &k, &m);
31     for(int i = 1; i <= k; ++i) {
32         int a, b;
33         scanf("%d%d", &a, &b);
34         v[a].push_back(b);
35         v[b].push_back(a);
36     }
37     dfs(1);
38     printf("%d
", ans);
39     return 0;
40 }