BZOJ_2582
首先来说，如果一个连通块里面的边的数量EN如果大于点的数量VN的话，那么显然是没办法保证每条边都属于一个顶点的，于是接下来就只剩两种情况要讨论了，一种是EN==VN，一种是EN==VN-1。
如果EN==VN，说明这个连通块里存在一个环，而环上的点是必须要选环上的边的，否则环上的边就会剩下，这样不妨把环拿下来，这时就会发现剩下的部分的分配方案是唯一的，而环这部分的分配方案是有且只有2种的。
如果EN==VN-1，可能着眼于哪个点拥有哪条边不是那么好计算，但换个思路就会非常清晰了，由于VN<EN，那么最后会有一个孤立点，我们不妨考虑这个孤立点是哪个点，而一旦确定某个点是孤立点之后，就可以把这个点拿出来了，这时就会发现剩下的部分的分配方案是唯一的，于是这种情况总的分配方案就是VN。
#include<stdio.h> #include<string.h> #define MAXD 100010 #define MAXM 200010 #define MOD 1000000007 typedef long long LL; int N, M, first[MAXD], e, next[MAXM], v[MAXM], vis[MAXD], cal[MAXM]; int VN, EN, ANS; void add(int x, int y) { v[e] = y; next[e] = first[x], first[x] = e ++; } void init() { memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0; for(int i = 0; i < M; i ++) { int x, y; scanf("%d%d", &x, &y); add(x, y), add(y, x); } } void dfs(int cur) { vis[cur] = 1, ++ VN; for(int i = first[cur]; i != -1; i = next[i]) if(!cal[i]) { cal[i] = cal[i ^ 1] = 1, ++ EN; if(!vis[v[i]]) dfs(v[i]); } } void solve() { ANS = 1; memset(vis, 0, sizeof(vis[0]) * (N + 1)); memset(cal, 0, sizeof(cal[0]) * e); for(int i = 1; i <= N; i ++) if(!vis[i]) { VN = EN = 0; dfs(i); if(EN > VN) { printf("0\n"); return ; } if(EN == VN) ANS = ANS * 2 % MOD; else ANS = (LL)ANS * VN % MOD; } printf("%d\n", ANS); } int main() { while(scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0; }