[Nescafe17] Magician

Magician

给你N个点, 连M次无向边, 每次连完边询问图上有多少个每个点的度数都为正偶数的子图。

解题报告

这是傻逼题啊! 或者说我是傻逼
考试的时候早就想到用环作为指数然后死也想不出下一步来啊 太差了 !
悲伤。
首先每一个满足题目条件的子图都必然是一堆没有横插边的’简单环’上的路径异或起来的。
如果在一个联通快内加入一条边, 那么只会增加一个简单环。
用并查集维护联通快然后算简单环数量, 算组合方案数(2^x)即可。
我果然是傻逼

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;
const int MOD = 1000000009;
int fa[200020];
int root (int u) {return fa[u]?root(fa[u]):u;}
int main () {
	int N, M;
	scanf("%d%d", &N, &M);
	int cur = 1;
	for(int i = 1; i<=M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		int ra = root(a), rb = root(b);
		if(ra == rb)
			cur = (cur<<1)%MOD;
		else fa[ra] = rb;
		printf("%d\n", cur-1);
	}
}