即删除一条边使图中不存在奇环。如果本身就是个二分图当然任意一条边都可以，先check一下。否则肯定要删除在所有奇环的交上的边。
考虑怎么找这些边。跑一遍dfs造出dfs树，找出返祖边构成的奇环。可以通过树上差分标记奇环上的边。
但是这显然只包含了一部分奇环。注意到如果某条在奇环上的边同时也在一个偶环上，一定可以找到一个不包含这条边的奇环。并且图中所有其他奇环都是由所找到的奇环加上偶环得到的，所以这就是充分的了。
数据中有重边自环，自环特判一下比较舒服，而任意一条重边都不可能在答案中（本身就是二分图除外）。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<map> #include<cassert> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 1000010 map<int,int> f[N]; int n,m,p[N],t=-1,fa[N<<1],deep[N],cnt[2][N<<1],delta[2][N],tot; struct data{int to,nxt; }edge[N<<1]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void dfs(int k,int from) { for (int i=p[k];~i;i=edge[i].nxt) if (edge[i].to!=from) if (deep[edge[i].to]&&deep[edge[i].to]<=deep[k]) { int op=deep[k]-deep[edge[i].to]&1; tot+=op^1;cnt[op][i]++; delta[op][k]++,delta[op][edge[i].to]--; } else if (!deep[edge[i].to]) { deep[edge[i].to]=deep[k]+1; dfs(edge[i].to,k); } } int Count(int op,int k,int from) { int s=0; for (int i=p[k];~i;i=edge[i].nxt) if (edge[i].to!=from&&!deep[edge[i].to]) { deep[edge[i].to]=deep[k]+1; int d=Count(op,edge[i].to,k); s+=d,cnt[op][i]+=d; } s+=delta[op][k]; return s; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4424.in","r",stdin); freopen("bzoj4424.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<=n*2;i++) fa[i]=i; memset(p,255,sizeof(p)); bool flag=1;int sc=0; for (int i=1;i<=m;i++) { int x=read(),y=read(); if (x!=y) { f[x][y]++,f[y][x]++; addedge(x,y);if (x!=y) addedge(y,x); fa[find(x)]=find(y+n),fa[find(x+n)]=find(y); if (find(x)==find(y)) flag=0; } else sc=sc?m+1:i; } if (sc) { if (!flag||sc>m) {cout<<0;return 0;} cout<<1<<endl<<sc; return 0; } if (flag) {cout<<m<<endl;for (int i=1;i<=m;i++) printf("%d ",i);return 0;} for (int i=1;i<=n;i++) if (!deep[i]) deep[i]=1,dfs(i,0); memset(deep,0,sizeof(deep)); for (int i=1;i<=n;i++) if (!deep[i]) deep[i]=1,Count(0,i,0); memset(deep,0,sizeof(deep)); for (int i=1;i<=n;i++) if (!deep[i]) deep[i]=1,Count(1,i,0); m=0; for (int i=0;i<=t;i++) m+=(cnt[0][i]==tot)&&(cnt[1][i]==0)&&(f[edge[i^1].to][edge[i].to]==1); cout<<m<<endl;for (int i=0;i<=t;i++) if ((cnt[0][i]==tot)&&(cnt[1][i]==0)&&(f[edge[i^1].to][edge[i].to]==1)) printf("%d ",i/2+1); return 0; }