正題

---

大意

一個圖有n個點，每次增加一條邊。每次增加一條邊之后統(tǒng)計每個點度數(shù)大于0且是偶數(shù)的子圖個數(shù)。

---

解題思路

首先滿足要求的子圖至少有一個環(huán)，然后我們考慮每加入一個環(huán)和別的環(huán)的判斷情況。每加入一個環(huán)的話我們會發(fā)現(xiàn)其實就是有若干個環(huán)之中選擇一些，我們可以用一個01串來表示是否選擇這個環(huán)，那么這個01串的全排列就是答案，當然要計算上只選一個環(huán)的情況。
用并查集判斷環(huán)，如果發(fā)現(xiàn)一個新環(huán)就統(tǒng)計ans，不然就連接。

---

代碼

#include<cstdio> using namespace std; int n,m,father[200001],ans,x,y; int find(int x) {if (father[x]==x) return x;return father[x]=find(father[x]); } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)father[i]=i;for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);if (find(x)!=find(y)){int fa=find(x),fb=find(y);//連接if (fa<fb) father[fa]=fb;else father[fb]=fa;}else ans=(ans*2+1)%1000000009;//統(tǒng)計答案printf("%d\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的jzoj3385-黑魔法之门【并差集】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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