Description

經(jīng)過了16個工作日的緊張忙碌，未來的人類終于收集到了足夠的能源。然而在與Violet星球的戰(zhàn)爭中，由于Z副官的愚蠢，地球的領(lǐng)袖applepi被邪惡的黑魔法師Vani囚禁在了Violet星球。為了重啟Nescafé這一宏偉的科技工程，人類派出了一支由XLk、Poet_shy和lydrainbowcat三人組成的精英隊伍，穿越時空隧道，去往Violet星球拯救領(lǐng)袖applepi。

applepi被囚禁的地點只有一扇門，當?shù)厝朔Q它為“黑魔法師之門”。這扇門上畫著一張無向無權(quán)圖，而打開這扇門的密碼就是圖中每個點的度數(shù)大于零且都是偶數(shù)的子圖的個數(shù)對1000000009取模的值。此處子圖?(V,?E)?定義為：點集V和邊集E都是原圖的任意子集，其中E中的邊的端點都在V中。

但是Vani認為這樣的密碼過于簡單，因此門上的圖是動態(tài)的。起初圖中只有N個頂點而沒有邊。Vani建造的門控系統(tǒng)共操作M次，每次往圖中添加一條邊。你必須在每次操作后都填寫正確的密碼，才能夠打開黑魔法師的牢獄，去拯救偉大的領(lǐng)袖applepi。 ?

Input

第一行包含兩個整數(shù)N和M。

接下來M行，每行兩個整數(shù)A和B，代表門控系統(tǒng)添加了一條無向邊?(A,?B)。

Output

輸出一共M行，表示每次操作后的密碼。

Sample Input

4 8
3 1
3 2
2 1
2 1
1 3
1 4
2 4
2 3

Sample Output

0
0
1
3
7
7
15
31
樣例解釋：
第三次添加之后，存在一個滿足條件的子圖?{1,?2,?3}（其中1,?2,?3是數(shù)據(jù)中邊的標號）。
第四次添加之后，存在三個子圖?{1,?2,?3}，{1,?2,?4}，{3,?4}。
子圖不一定連通。舉另外一個例子，例如點(1、2、3)，(4、5、6)分別組成一個三元環(huán)，則圖中有三個所求子圖。

Data Constraint

對于30%?的數(shù)據(jù)，N,?M≤10。

對于100%?的數(shù)據(jù)，N≤200000，M≤300000。

?

題目大意：有n個點，進行m次加邊操作，每次操作之后輸出當前圖中的子集是一個或多個環(huán)的個數(shù)

題解：

考慮在第一次加邊之后我們得到了一條“線段”，我們將其看成是一棵樹（事實上它就是樹）。發(fā)現(xiàn)當我們把樹變成一顆環(huán)基樹的時候就一定會產(chǎn)生一個環(huán)。在不斷的加邊的過程中，我們發(fā)現(xiàn)

每一個非樹上邊的子集都對應(yīng)了一個我們統(tǒng)計的子圖。那么我們的答案就是2^t-1，t就是非樹上邊的條數(shù)（沒有樹上邊的時候沒有環(huán)，因此減1）。那么怎么搞出樹上邊的條數(shù)呢？考慮用并查集維護，支持合并操作。

值得注意的是，我們統(tǒng)計的是子集的個數(shù)，而不是環(huán)的個數(shù)

代碼非常的好寫

#include <iostream> #include <cstdio> using namespace std;const int N=2e5+50; const int P=1000000009; int n,m,sum; int fa[N]; long long ans=1; int read() {int x=0,f=1; char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f; } int find(int k) {if (fa[k]!=k) fa[k]=find(fa[k]);return fa[k]; } int main() {n=read();m=read();for (int i=1;i<=n;i++) fa[i]=i;for (int i=1;i<=m;i++){int x=read(),y=read();int fx=find(x),fy=find(y);if (fx==fy) ans=ans<<1;else fa[fx]=fy;ans%=P;printf("%lld\n",ans-1);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xxzh/p/9304633.html

總結(jié)

以上是生活随笔為你收集整理的[JZOJ3385] [NOIP2013模拟] 黑魔法师之门 解题报告(并查集)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。