Friends
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5305
Mean:
n个人，m对朋友关系，每个人的朋友中又分为在线好友和不在线好友，对于每个人都要保证在线好友和不在线好友一样多，求方案数有多少种。
analyse:
我们用m对关系建立一个无向图（存边即可），同时统计每个节点的度。
首先可以确定的是：如果某个节点的度是奇数，很显然answer=0。
将每个节点的度分为两组：online和offonline。
初始时，每个节点的online和offonline是相等的。
然后就是dfs统计答案。
如何统计呢？
dfs统计答案的实质就是枚举每一条边的两种属性（online和offonline）.
如果枚举得到的状态能满足条件，在程序中可以走到m+1状态，此时是一种答案，ans++。
在dfs时，我们把每条边对应的两个节点的online值同增同减，且回溯时将减掉的online加回来，这样就保证了online和offonline在相同数量的边的情况下是相等的。
这种做法还是很巧妙的。
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-24-08.09
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int n , m , ans;
int time [ 10 ], online [ 10 ], offonline [ 10 ];
struct edge
{
int u , v;
} e [ 30 ];
void DFS( int x )
{
if( x == m + 1 )
{
ans ++;
return;
}
int u = e [ x ]. u;
int v = e [ x ]. v;
if( online [ u ] && online [ v ] )
{
online [ u ] --;
online [ v ] --;
DFS( x + 1 );
online [ u ] ++;
online [ v ] ++;
}
if( offonline [ u ] && offonline [ v ] )
{
offonline [ u ] --;
offonline [ v ] --;
DFS( x + 1 );
offonline [ u ] ++;
offonline [ v ] ++;
}
return ;
}
int main()
{
ios_base :: sync_with_stdio( false );
cin . tie( 0 );
int t;
cin >> t;
while( t -- )
{
ans = 0;
memset( time , 0 , sizeof( time ) );
memset( e , 0 , sizeof( e ) );
memset( online , 0 , sizeof( online ) );
memset( offonline , 0 , sizeof( offonline ) );
cin >> n >> m;
for( int i = 1; i <= m; ++ i )
{
cin >> e [ i ]. u >> e [ i ]. v;
time [ e [ i ]. u ] ++ , time [ e [ i ]. v ] ++;
}
bool f = true;
for( int i = 1; i <= n; ++ i )
{
online [ i ] = offonline [ i ] = time [ i ] / 2;
if( time [ i ] & 1 )
{
f = false;
break;
}
}
if( ! f )
{
cout << 0 << endl;
continue;
}
DFS( 1 );
cout << ans << endl;
}
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-24-08.09
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int n , m , ans;
int time [ 10 ], online [ 10 ], offonline [ 10 ];
struct edge
{
int u , v;
} e [ 30 ];
void DFS( int x )
{
if( x == m + 1 )
{
ans ++;
return;
}
int u = e [ x ]. u;
int v = e [ x ]. v;
if( online [ u ] && online [ v ] )
{
online [ u ] --;
online [ v ] --;
DFS( x + 1 );
online [ u ] ++;
online [ v ] ++;
}
if( offonline [ u ] && offonline [ v ] )
{
offonline [ u ] --;
offonline [ v ] --;
DFS( x + 1 );
offonline [ u ] ++;
offonline [ v ] ++;
}
return ;
}
int main()
{
ios_base :: sync_with_stdio( false );
cin . tie( 0 );
int t;
cin >> t;
while( t -- )
{
ans = 0;
memset( time , 0 , sizeof( time ) );
memset( e , 0 , sizeof( e ) );
memset( online , 0 , sizeof( online ) );
memset( offonline , 0 , sizeof( offonline ) );
cin >> n >> m;
for( int i = 1; i <= m; ++ i )
{
cin >> e [ i ]. u >> e [ i ]. v;
time [ e [ i ]. u ] ++ , time [ e [ i ]. v ] ++;
}
bool f = true;
for( int i = 1; i <= n; ++ i )
{
online [ i ] = offonline [ i ] = time [ i ] / 2;
if( time [ i ] & 1 )
{
f = false;
break;
}
}
if( ! f )
{
cout << 0 << endl;
continue;
}
DFS( 1 );
cout << ans << endl;
}
return 0;
}
/*
*/
