Poetize I 黑魔法师之门

wjh15101051's space

卧薪尝胆，厚积薄发。

Poetize I 黑魔法师之门

Date: Thu Sep 20 16:37:51 CST 2018

In Category: NoCategory

Description：

给一个点的集合，支持加边，询问图中每个点的度数大于零且都是偶数的子图的个数。

$1\le n \le200000$

Solution：

找规律发现每当把两个已经连起来的点连一条边时， $tmp=tmp\times 2$ ，最后的答案是 $tmp-1$ 。

至于为什么，每当把这样两个点连起来时，会产生一个新的元环，即不能由别的几个环合并再去掉公共部分得到的环，每次的方案数就是 $2$ 的元环个数次方，再减去一个都不选的情况，即 $1$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000009

int n,m;

#define MAXN 200010

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int ans = 1;

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= n;++i)f[i] = i; 

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		int p = find(a),q = find(b);

		if(p == q)ans = ans * 2 % MOD;

		else f[p] = q;

		printf("%d\n",ans - 1);

	}

	return 0;

}

In tag: 数据结构-并查集

wjh15101051