hdu 5305 Friends (dfs)
dfs 1A
/*************************************************************************
> File Name: code/whust/#9/K.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月05日 星期三 15时02分30秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24int n ,m,ans;
25int d[50];
26int on[50],off[50];
27int u[50],v[50];
1bool ok(int x,int y)
2{
3 if ( !d[x] && !d[y] && on[x] == off[x] && on[y] == off[y] )
4 return true;
5 if ( !d[x] && d[y] && on[x] == off[x] )
6 return true;
7 if ( d[x] && !d[y] && on[y] == off[y] )
8 return true;
9 if ( d[x] && d[y] )
10 return true;
11 return false;
12}
1void dfs ( int i)
2{
3 if (i==m)
4 {
5 ans++;
6 return;
7 }
8 int x = u[i];
9 int y = v[i];
10 d[x]--;
11 d[y]--;
12 on[x]++;
13 on[y]++;
14 if (ok(x,y))
15 dfs (i+1);
16 on[x]--;on[y]--;
17 off[y]++;off[x]++;
18 if ( ok( x,y))
19 dfs (i+1);
20 off[y]--;
21 off[x]--;
22 d[x]++;
23 d[y]++;
24}
1int main ( )
2{
3 int T;
4 cin>>T;
5 while ( T-- )
6 {
7 ans = 0;
8 scanf ("%d %d",&n,&m);
9 memset (d,0,sizeof(d));
10 memset (on,0,sizeof(on));
11 memset (off,0,sizeof(off));
12 for ( int i = 0 ; i < m ; i++ )
13 {
14 scanf ("%d%d",&u[i],&v[i]);
15 d[u[i]]++;
16 d[v[i]]++;
17 }
18 dfs (0);
19 printf ( "%d\n" , ans );
20 }
21}