經過了16 個工作日的緊張忙碌，未來的人類終于收集到了足夠的能源。然而在與Violet星球的戰爭中，由于Z 副官的愚蠢，地球的領袖applepi 被邪惡的黑魔法師Vani 囚禁在了Violet 星球。為了重啟Nescafé這一宏偉的科技工程，人類派出了一支由XLk、Poet_shy 和lydrainbowcat 三人組成的精英隊伍，穿越時空隧道，去往Violet 星球拯救領袖applepi。applepi 被囚禁的地點只有一扇門，當地人稱它為“黑魔法師之門”。這扇門上畫著一張無向無權圖，而打開這扇門的密就是圖中每個點的度數大于零且都是偶數的子圖的個數對1000000009 取模的值。此處子圖 (V, E) 定義為：點集V 和邊集E 都是原圖的任意子集，其中E 中的邊的端點都在V 中。但是Vani 認為這樣的密碼過于簡單，因此門上的圖是動態的。起初圖中只有N 個頂點而沒有邊。Vani 建造的門控系統共操作M 次，每次往圖中添加一條邊。你必須在每次操作后都填寫正確的密碼，才能夠打開黑魔法師的牢獄，去拯救偉大的領袖applepi。

?

第一行包含兩個整數?N?和?M。接下來?M?行，每行兩個整數?A?和?B，代表門控系統添加了一條無向邊(A,?B)。

?

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

?

輸入示例：

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

輸出示例：

0
0
1
3
7
7
15
31

?

數據范圍：N≤200000?，M≤300000?。

?

提醒：子圖不一定連通。舉另外一個例子，例如點(1、2、3)，(4、5、6)分別組成一個三元環，則圖中有三個所求子圖。

?

題解：

并查集維護，如果兩點在同一集合中，則 ?ans=ans*2+1。

 1 #include<iostream>
 2 using namespace std;
 3 int a,m,tem,tem1;
 4 int n[200005];
 5 int find(int x) {return x==n[x]?x:n[x]=find(n[x]);}
 6 int read()
 7 {
 8     int x=0,f=1;
 9     char ch=getchar();
10     while(ch<'0'||ch>'9')
11     {
12         f=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9')
16     {
17         x=x*10+ch-'0';
18         ch=getchar();
19     }
20     return f*x;
21 }
22 int main()
23 {
24     a=read();
25     m=read();
26     int ans=0;
27     for(int i=0;i<a;i++) n[i]=i;
28     for(int i=0;i<m;i++)
29     {
30         tem=read();
31         tem1=read();
32         int temp=find(tem),temp1=find(tem1);
33         if(temp!=temp1) {n[temp]=temp1;}
34         else
35         {
36             ans+=ans+1;
37             ans%=1000000009;
38         }
39         printf("%d\n",ans);
40     }
41     //system("pause>nul");
42     return 0;
43 }

C++ Anser

?

轉載于:https://www.cnblogs.com/nightfury/p/4983066.html

總結

以上是生活随笔為你收集整理的刷过一题之黑魔法师之门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。