题意：给出一幅无向图。依次对边染白色或黑色，使得每个点所关联的白边和黑边数目相同。问有多少种染色方法。
思路：
搜索题。强行暴力搜必定超时。枚举点来搜索也不好写。因此枚举边。
记录每个点的度数，若有点的度数为奇数，直接输出0。否则，将所有点的度数除以2，得到每个点关联的白边数目和黑边数目，此为剪枝。
代码如下：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int t,n,m,a[30],b[30],d[10]; int B[30],W[30],ans; void dfs(int k){ if(k==m){ ans++;return; } int u=a[k],v=b[k]; if(B[u]<d[u]&&B[v]<d[v]){ B[u]++,B[v]++; dfs(k+1); B[u]--,B[v]--; } if(W[u]<d[u]&&W[v]<d[v]){ W[u]++,W[v]++; dfs(k+1); W[u]--,W[v]--; } } int main(){ scanf("%d",&t); while(t--){ bool flag=true; scanf("%d%d",&n,&m); memset(d,0,sizeof(d)); for(int i=0;i<m;i++){ scanf("%d%d",&a[i],&b[i]); d[a[i]]++;d[b[i]]++; } for(int i=1;i<=n;i++){ if(d[i]&1) flag=false; d[i]/=2; } if(!flag){ puts("0"); continue; } memset(W,0,sizeof(W)); memset(B,0,sizeof(B)); ans=0; dfs(0); printf("%d\n",ans); } return 0; }
原文：http://www.cnblogs.com/names-yc/p/4703068.html
