DFS HDU 5305 Friends

 1 /*
 2     题意：每个点都要有偶数条边，且边染色成相同的两部分，问能有多少种染色方法
 3     DFS+剪枝：按照边数来DFS，每种染色数为该点入度的一半，还有如果点不是偶数边就不DFS
 4             这是别人的DFS，写的精简强大，膜拜之。。。
 5 */
 6 #include <cstdio>
 7 #include <algorithm>
 8 #include <cstring>
 9 #include <vector>
10 using namespace std;
11 
12 const int MAXN = 33;
13 const int INF = 0x3f3f3f3f;
14 int d[MAXN], c1[MAXN], c2[MAXN];
15 int a[MAXN], b[MAXN];
16 int n, m, ans;
17 
18 void DFS(int k) {
19     if (k == m + 1) {
20         ans++;  return ;
21     }
22     int u = a[k], v = b[k];
23     if (c1[u] < d[u] && c1[v] < d[v])   {
24         c1[u]++;    c1[v]++;
25         DFS (k + 1);
26         c1[u]--;    c1[v]--;
27     }
28     if (c2[u] < d[u] && c2[v] < d[v])   {
29         c2[u]++;    c2[v]++;
30         DFS (k + 1);
31         c2[u]--;    c2[v]--;
32     }
33 }
34 
35 int main(void)  {       //HDOJ 5305 Friends
36     //freopen ("F.in", "r", stdin);
37 
38     int t;  scanf ("%d", &t);
39     while (t--) {
40         memset (d, 0, sizeof (d));
41         scanf ("%d%d", &n, &m);
42         for (int i=1; i<=m; ++i)    {
43             scanf ("%d%d", &a[i], &b[i]);
44             d[a[i]]++; d[b[i]]++;
45         }
46         
47         bool flag = true;
48         for (int i=1; i<=n; ++i)    {
49             if (d[i] & 1)   {
50                 flag = false;   break;
51             }
52             d[i] /= 2;
53         }
54 
55         if (!flag)  {
56             puts ("0"); continue;
57         }
58         memset (c1, 0, sizeof (c1));
59         memset (c2, 0, sizeof (c2));
60         ans = 0;    DFS (1);
61         printf ("%d
", ans);
62     }
63 
64     return 0;
65 }
编译人生，运行世界！