bzoj 4424: Cf19E Fairy

.

题意：在一个无向图中，问有哪些边满足删掉它以后这个图是二分图（删的是一条边而不是很多条边这里理解错题意卡了好久QAQ）
题解：dfs找环。二分图有个性质：所有的环都是偶环。我们要把一个图变成二分图就需要消掉所有的奇环，也就是说，所有奇环的交就是答案。没有奇环就是每个都可以删。还有，cf不卡输出，bzoj卡。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,fst[1000010],num=0,dep[1000010],sum[1000010],cnt=0,hh,snum=0,self;
struct edge
{
    int x,y,id,n;
}e[2000010];
bool v[1000010];
vector<int>ans;

void ins(int x,int y,int id)
{
    e[++num]={x,y,id,fst[x]};
    fst[x]=num;
}
void dfs(int x,int fr)
{
    v[x]=1;
    int f=e[fr].x;
    dep[x]=dep[f]+1;
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        if(e[i].id==e[fr].id)
        continue;
        if(!v[y])
        {
            dfs(y,i);
            sum[x]+=sum[y];
        }
        else if(dep[y]<=dep[x])
        {
            if(!(dep[x]-dep[y]&1))
            {
                sum[y]--;
                sum[x]++;
                cnt++;
                hh=e[i].id;
            }
            else
            {
                sum[y]++;
                sum[x]--;
            }
        }
    }
}
void fd(int x,int fr)
{
    v[x]=1;
    if(sum[x]==cnt)
    ans.push_back(e[fr].id);
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        if(!v[y])
        fd(y,i);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)
        {
            snum++;
            self=i;
        }
        else
        {
            ins(x,y,i);
            ins(y,x,i);
        }
    }
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;i++)
    if(!v[i])
    dfs(i,0);
    if(cnt==0)
    {
        if(snum==1)
        {
            printf("1\n%d",self);
        }
        else if(snum>1)
        {
            puts("0");
        }
        else
        {
            printf("%d\n",m);
            for(int i=1;i<m;i++)
            printf("%d ",i);
            printf("%d",m);
        }
    }
    else
    {
        if(snum)
        {
            puts("0");
        }
        else
        {
            memset(v,0,sizeof(v));
            for(int i=1;i<=n;i++)
            if(!v[i])
            fd(i,0);
            if(cnt==1)
            ans.push_back(hh);
            sort(ans.begin(),ans.end());
            printf("%d\n",ans.size());
            if(ans.size())
            {
                printf("%d",ans[0]);
                for(int i=1;i<ans.size();i++)
                printf(" %d",ans[i]);
            }

        }
    }
}