记录编号	253002	评测结果	AAAAAAAAAA
题目名称	[Nescafé 17] 黑魔法师之门	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.367 s
提交时间	2016-04-21 14:02:16	内存使用	1.81 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
#define mod 1000000009

const int maxl=200010;
int pow(int n){//求2^n-1 
	long long answer=1,x=2;
	for (int i=n;i>0;i/=2){
		if ((i&1)==1) answer=(answer*x)%mod;
		x=(x*x)%mod;
	}
	return answer-1;
}

int n,m,i,cnt,fa[maxl],f,t,a,b,size[maxl];
//size[i]表示以i为代表的并查集上的边数+1-点数，即存在的不能被若干个不同环的和或差表示的环的个数 
//cnt记录全图环的个数 
int find(int x){
	return (fa[x]==x?x:fa[x]=find(fa[x]));
}

int main()
{
	freopen("magiciana.in","r",stdin);
	freopen("magiciana.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=1;i<=m;i++){
		scanf("%d%d",&f,&t);
		a=find(f);b=find(t);
		if (a!=b){
			cnt=(mod+cnt-size[a])%mod;
			cnt=(mod+cnt-size[b])%mod;
			fa[b]=a;
			size[a]=(size[a]+size[b])%mod;
			cnt=(cnt+size[a])%mod;
		}
		else cnt++,size[a]++;
		printf("%d\n",pow(cnt));
	}
	return 0;
}