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); } }
Join the discussion