https://www.zybuluo.com/ysner/note/1294323
题面
删去一条边，使整张图成为二分图。
- (n,mleq10^4)
解析
我一开始想通过一遍(dfs)找出图中所有环来着。。。
显然一条边可以从属于多个环，因此一遍(DFS)肯定找不全。
怎么办呢?
据说可以树上差分。
就是在(dfs)过程中，把边看成点建在新图中，每次把扫到的前后两条边在新图中连起来。
然后在形成奇环的时候，在当前点标号(+1)，在对面那一边（不是自己来的那条）处标号(-1)。偶环反过来。
同时如果出现一个奇环，就(++tot)。
最后从下往上上传标记，若有边标号为(tot)，那就说明它只属于所有奇环，不属于偶环，符合题目要求。
好妙啊。
记得奇环个数为(0/1)时要特判。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,m,a[N],sta[N],top,w[N],in[N],pos[N],tot,lk[N];
bool vis[N];
struct Edge{int to,nxt,id;};
struct dag
{
Edge e[N<<1];
int h[N],cnt;
il dag(){memset(h,-1,sizeof(h));cnt=0;}
il void add(re int u,re int v,re int id)
{
e[++cnt]=(Edge){v,h[u],id};h[u]=cnt;
e[++cnt]=(Edge){u,h[v],id};h[v]=cnt;
}
}A,B;
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void dfs(re int u,re int fa,re int las)
{
sta[++top]=u;pos[u]=top;vis[u]=1;
for(re int i=A.h[u];i+1;i=A.e[i].nxt)
{
re int v=A.e[i].to,id=A.e[i].id;
if(las==id) continue;
if(!lk[id]) lk[id]=1,B.add(las,id,0);
if(!pos[v]) in[v]=id,dfs(v,u,id);
else if(vis[v])
{
if((pos[u]-pos[v])&1) --w[id],++w[in[v]];
else ++w[id],--w[in[v]],++tot;
}
}
vis[u]=0;--top;
}
il void dfs(re int u,re int fa)
{
for(re int i=B.h[u];i+1;i=B.e[i].nxt)
{
re int v=B.e[i].to;
if(v==fa) continue;
dfs(v,u);
w[u]+=w[v];
}
if(w[u]==tot) sta[++top]=u;
}
int main()
{
n=gi();m=gi();
fp(i,1,m)
{
re int u=gi(),v=gi();
A.add(u,v,i);
}
fp(i,1,n) if(!pos[i]) dfs(i,0,0);
top=0;dfs(0,-2);
if(!tot) {printf("%d
",m);fp(i,1,m) printf("%d ",i);puts("");return 0;}
sort(sta+1,sta+1+top);
printf("%d
",top);
fp(i,1,top) printf("%d ",sta[i]);puts("");
return 0;
}