hdu 5305 Friends （dfs）
dfs 1A
1/*************************************************************************
2 > File Name: code/whust/#9/K.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月05日 星期三 15时02分30秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31int n ,m,ans;
32int d[50];
33int on[50],off[50];
34int u[50],v[50];
35
36bool ok(int x,int y)
37{
38 if ( !d[x] && !d[y] && on[x] == off[x] && on[y] == off[y] )
39 return true;
40 if ( !d[x] && d[y] && on[x] == off[x] )
41 return true;
42 if ( d[x] && !d[y] && on[y] == off[y] )
43 return true;
44 if ( d[x] && d[y] )
45 return true;
46 return false;
47}
48
49void dfs ( int i)
50{
51 if (i==m)
52 {
53 ans++;
54 return;
55 }
56 int x = u[i];
57 int y = v[i];
58 d[x]--;
59 d[y]--;
60 on[x]++;
61 on[y]++;
62 if (ok(x,y))
63 dfs (i+1);
64 on[x]--;on[y]--;
65 off[y]++;off[x]++;
66 if ( ok( x,y))
67 dfs (i+1);
68 off[y]--;
69 off[x]--;
70 d[x]++;
71 d[y]++;
72}
73
74int main ( )
75{
76 int T;
77 cin>>T;
78 while ( T-- )
79 {
80 ans = 0;
81 scanf ("%d %d",&n,&m);
82 memset (d,0,sizeof(d));
83 memset (on,0,sizeof(on));
84 memset (off,0,sizeof(off));
85 for ( int i = 0 ; i < m ; i++ )
86 {
87 scanf ("%d%d",&u[i],&v[i]);
88 d[u[i]]++;
89 d[v[i]]++;
90 }
91 dfs (0);
92 printf ( "%d\n" , ans );
93 }
94}