http://www.lydsy.com/JudgeOnline/problem.php?id=4424
图是二分图的条件：没有奇环
所以，如果图不存在奇环，删除任意一条边都可以
如果存在奇环，
对于树边来说：
那么可能可以删除的边一定在所有奇环的交集内
而且这条边不能在偶环内
因为如果一条边既是奇环上的一条边，又是偶环上的一条边
删除这条边后，这个奇环和偶环会合并成一个新的奇环
所以最终的答案= 奇环的交集-偶环的并集
对于非树边来说：
如果只有一个奇环，那么可以删除构成环的这条非树边
树边和非树边的判断：并查集
奇环交与偶环并：差分，统计树上后缀和
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 1000001 int e[N][],ty[N]; int tot=;
int front[N],nxt[N<<],to[N<<],id[N<<]; int F[N]; int maxd;
int fa[N][]; int dep[N]; int odd_cir,sum[N]; int ans_tot,ans[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int find(int i) { return F[i]==i ? i : F[i]=find(F[i]); } void add(int u,int v,int num)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; id[tot]=num;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; id[tot]=num;
} void dfs(int u)
{
for(int i=;i<=maxd;++i) fa[u][i]=fa[fa[u][i-]][i-];
int t;
for(int i=front[u];i;i=nxt[i])
{
t=to[i];
if(t==fa[u][]) continue;
dep[t]=dep[u]+;
fa[t][]=u;
dfs(t);
}
} int cal(int x)
{
for(int i=front[x];i;i=nxt[i])
if(to[i]!=fa[x][])
{
cal(to[i]);
if(sum[to[i]]==odd_cir) ans[++ans_tot]=id[i];
sum[x]+=sum[to[i]];
}
} int get_lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
int cnt=dep[u]-dep[v];
for(int i=maxd;i>=;--i)
if(cnt&(<<i)) u=fa[u][i];
if(u==v) return u;
for(int i=maxd;i>=;--i)
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][];
} int main()
{
int n,m;
int u,v,fu,fv;
read(n); read(m);
for(int i=;i<=n;++i) F[i]=i;
for(int i=;i<=m;++i)
{
read(u); read(v);
fu=find(u); fv=find(v);
if(fu!=fv)
{
ty[i]=;
F[fu]=fv;
add(u,v,i);
}
e[i][]=u; e[i][]=v;
}
maxd=log(n)/log();
for(int i=;i<=n;++i)
if(find(i)==i) dep[i]=,dfs(i);
int self=;
int lca;
for(int i=;i<=m;++i)
{
u=e[i][]; v=e[i][];
if(u==v && self) { printf(""); return ; }
if(u==v) { self=i; continue; }
if(!ty[i])
{
lca=get_lca(u,v);
if((dep[u]-dep[lca]+dep[v]-dep[lca])&)
{
sum[v]--;
sum[u]--;
sum[lca]+=;
}
else
{
ty[i]=;
odd_cir++;
sum[v]++;
sum[u]++;
sum[lca]-=;
}
}
}
if(self)
{
if(!odd_cir) printf("1\n%d",self);
else printf("");
return ;
}
if(!odd_cir)
{
printf("%d\n",m);
for(int i=;i<m;++i) printf("%d ",i);
if(m) printf("%d",m);
return ;
}
for(int i=;i<=n;++i)
if(find(i)==i) cal(i);
if(odd_cir==)
for(int i=;i<=m;++i)
if(ty[i]==)
{
ans[++ans_tot]=i;
break;
}
sort(ans+,ans+ans_tot+);
printf("%d\n",ans_tot);
for(int i=;i<ans_tot;++i) printf("%d ",ans[i]);
if(ans_tot) printf("%d",ans[ans_tot]);
}
4424: Cf19E Fairy
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 740 Solved: 187
[Submit][Status][Discuss]
Description
给定 n 个点，m 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成
一个二分图。
Input
第 1 行包含两个整数 n，m。分别表示点数和边数。
第 2 到 m+1 行每行两个数 x，y 表示有一条（x,y）的边。
Output
输出第一行一个整数，表示能删除的边的个数。
接下来一行按照从小到大的顺序输出边的序号。
Sample Input
4 4
1 2
1 3
2 4
3 4
1 2
1 3
2 4
3 4
Sample Output
4
1 2 3 4
1 2 3 4
HINT
100%的数据，n,m<=1000000