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}