CF19E Fairy

图论 二分图 树上差分

题面

删去一条边，使整张图成为二分图。

• $n,m\leq10^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\n",m);fp(i,1,m) printf("%d ",i);puts("");return 0;}
  sort(sta+1,sta+1+top);
  printf("%d\n",top);
  fp(i,1,top) printf("%d ",sta[i]);puts("");
  return 0;
}