题目概述

有 $n$ 个点 $m$ 条边，问有多少边删除了之后让原图是二分图。

解题报告

远古CF题。删除一条边可以考虑分治，然后用LCT判断有没有奇环就行了。

这是斯波做法，时间复杂度 $O(nlog_2^2n)$ 还有大常数。过不了BZOJ4424加强版。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000000,maxm=1000000;

int n,m,x[maxm+5],y[maxm+5],ans;bool now=true,vis[maxn+5],us[maxn+5];
int son[maxn+5][2],fa[maxn+5],si[maxn+5];bool flip[maxn+5];

#define is_ro(p) ((p)!=son[fa[p]][0]&&(p)!=son[fa[p]][1])
#define Son(p) ((p)==son[fa[p]][1])
inline void Pushup(int p) {si[p]=si[son[p][0]]+1+si[son[p][1]];}
inline void Rotate(int t){
    int p=fa[t],d=Son(t)^1;son[p][d^1]=son[t][d];son[t][d]=p;
    Pushup(p);Pushup(t);if (!is_ro(p)) son[fa[p]][Son(p)]=t;
    if (son[p][d^1]) fa[son[p][d^1]]=p;fa[t]=fa[p];fa[p]=t;
}
inline void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;}
inline void Pushdown(int p) {if (flip[p]) flip[p]^=1,Addflip(son[p][0]),Addflip(son[p][1]);}
inline void Splay(int p){
    static int top,stk[maxn+5];stk[top=1]=p;;
    for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
        if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
}
inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);}
inline void Makero(int p) {Access(p);Splay(p);Addflip(p);}
inline void Link(int x,int y) {Makero(x);fa[x]=y;}
inline void Cut(int x,int y) {Makero(x);Access(y);Splay(y);fa[x]=son[y][0]=0;}
inline int getfa(int x) {Access(x);Splay(x);while (son[x][0]) x=son[x][0];return x;}
inline int Size(int x,int y) {Makero(x);Access(y);Splay(x);return si[x];}
void Solve(int L,int R){
    if (L==R) {ans+=(vis[L]=now);return;}int mid=L+(R-L>>1);bool tem=now;
    for (int i=L;i<=mid;i++)
        if (getfa(x[i])==getfa(y[i])) {if (Size(x[i],y[i])&1) now=false;us[i]=true;} else Link(x[i],y[i]);
    if (now) Solve(mid+1,R);now=tem;for (int i=L;i<=mid;i++) if (us[i]) us[i]=false; else Cut(x[i],y[i]);
    for (int i=mid+1;i<=R;i++)
        if (getfa(x[i])==getfa(y[i])) {if (Size(x[i],y[i])&1) now=false;us[i]=true;} else Link(x[i],y[i]);
    if (now) Solve(L,mid);now=tem;for (int i=mid+1;i<=R;i++) if (us[i]) us[i]=false; else Cut(x[i],y[i]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);if (!m) return puts("0"),0;
    for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);Solve(1,m);printf("%d\n",ans);
    for (int i=1,fr=true;i<=m;i++) if (vis[i]) {fr?fr=false:putchar(' ');printf("%d",i);};return 0;
}