[CF19E]Fairy

给定一张n个点m条边的无向图，求删除哪一条边后，能够确保构成一个二分图，输出所有可能

解法：我们知道二分图的性质是没有奇环，这道题我们也应该从这个方面入手来考虑。

如果没有奇环的话我们当然想怎么删就怎么删，毕竟两个偶环删一条边不会出来一个奇环

如果存在奇环，那么我们删边一定要删奇环上的边，而且这条边必须是所有奇环的并

还要考虑的是，如果这条边还属于某个偶环，删掉这条边后图中还会形成一个新的奇环，因此删除的边还不能属于偶环

这种关于返祖边的题目用树上差分来处理就可以

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define M 10010

 using namespace std;

 struct point{

     int from,to,next;

 }e[M<<];

 struct Link{

     int odd,even;

     bool flag;

     int from,to;

 }link[M];

 int n,m,num,cnt,tot;

 int  head[M],odd[M],even[M],ans[M],deep[M];

 bool vis[M];

 void add(int from,int to)

 {

     e[num].next=head[from];

     e[num].from=from;

     e[num].to=to;

     head[from]=num++;

 }

 void dfs(int x)

 {

     vis[x]=true;

     for(int i=head[x];~i;i=e[i].next)

     {

         int to=e[i].to;

         if(!vis[to])

         {

             link[i>>].flag=true;

             deep[to]=deep[x]+;//树边

             dfs(to);

         }

     }

 }

 void DFS(int x)

 {

     vis[x]=true;

     for(int i=head[x];~i;i=e[i].next)

     {

         int to=e[i].to;

         if(!vis[to])//树边

         {

             DFS(to);

             odd[x]+=odd[to];

             even[x]+=even[to];

             link[i>>].odd=odd[to];

             link[i>>].even=even[to];

         }

     }

 }

 int main()

 {

     memset(head,-,sizeof(head));

     scanf("%d%d",&n,&m);

     for(int i=;i<m;i++)

     {

         scanf("%d%d",&link[i].from,&link[i].to);

         add(link[i].from,link[i].to);

         add(link[i].to,link[i].from);

     }

     for(int i=;i<=n;i++)

         if(!vis[i])

         {

             deep[i]=;

             dfs(i);

         }

     for(int i=;i<m;i++)

     {

         if(link[i].flag) continue;

         int u=link[i].from,v=link[i].to;

         if(deep[u]>deep[v]) swap(u,v);//u为祖先

         if((deep[v]-deep[u])&) even[u]--,even[v]++;

         else odd[u]--,odd[v]++,link[i].odd++,tot++;

     }

     if(!tot)

     {

         printf("%d\n",m);

         for(int i=;i<=m;i++) printf("%d ",i);

         return ;

     }

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++)

         if(!vis[i])

             DFS(i);

     for(int i=;i<m;i++)

     {

         if(link[i].flag)

         {

             if(!link[i].even&&link[i].odd==tot) ans[++cnt]=i+;//是奇环的并且不在偶环上

         }

         else if(tot==&&link[i].odd) ans[++cnt]=i+;//如果只有一个奇环，奇环中的边都可删

     }

     printf("%d\n",cnt);

     for(int i=;i<=cnt;i++) printf("%d ",ans[i]);

     return ;

 }