2015 Multi-University Training Contest 2 1006 Friends 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]--;

           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;