正題

題目鏈接:https://www.luogu.com.cn/problem/CF19E

---

題目大意

給出$n$個點$m$條邊的一張無向圖，求有多少條邊去掉后可以使得圖變成一張二分圖。

$1\le n,m\le 10^4$

---

解題思路

雖然線段樹分治可以暴力草過去但是考慮點智慧的做法。

眾所周知沒有奇環(huán)是圖是二分圖的充要條件，所以答案就是奇環(huán)的交。

顯然無法考慮所有的奇環(huán)，但是我們可以考慮一下簡單奇環(huán)。

先隨便跑出一個生成樹，然后枚舉所有非樹邊考慮其在樹上的環(huán)，只考慮樹邊的話答案肯定是所有簡單奇環(huán)的交。并且這條邊不能出現(xiàn)在一個枚舉出的偶環(huán)上，因為如果這條邊即在一個奇環(huán)又在一個偶環(huán)上，那么這兩個環(huán)的不交部分一定是一個奇環(huán)，所以這條邊就不成立了。

然后對于非樹邊，顯然條件就是這條邊必須得是唯一一個樹上奇環(huán)的邊。

用$dfs$搜出生成樹，此時所有的非樹邊都是返祖邊，這樣我們就可以用樹上差分計算樹邊的條件了。

時間復雜度$O(n+m)$（不算答案用的排序）

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e4+10; struct node{int to,next,w; }a[N<<1]; int n,m,tot,cnt,ant,last; int ls[N],v[N],s[N],from[N],ans[N]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;return; } void dfs(int x){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if((i^1)==from[x])continue;if(v[y]&&v[x]>v[y]){if((v[x]-v[y])&1)s[x]--,s[y]++;else s[x]++,s[y]--,cnt++,last=a[i].w;}else if(!v[y]){v[y]=v[x]+1;from[y]=i;dfs(y);s[x]+=s[y];}}return; } int main() {scanf("%d%d",&n,&m);tot=1;for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);addl(x,y,i);addl(y,x,i);}for(int i=1;i<=n;i++)if(!v[i])v[i]=1,dfs(i);if(!cnt){printf("%d\n",m);for(int i=1;i<=m;i++)printf("%d ",i);return 0;}if(cnt==1)ans[++ant]=last;for(int i=1;i<=n;i++)if(s[i]==cnt)ans[++ant]=a[from[i]].w;sort(ans+1,ans+1+ant);ant=unique(ans+1,ans+1+ant)-ans-1;printf("%d\n",ant);for(int i=1;i<=ant;i++)printf("%d ",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的CF19E-Fairy【树形结构,差分】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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