bzoj千题计划229：bzoj4424: Cf19E Fairy

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

Sample Output

4
1 2 3 4

HINT

100%的数据，n,m<=1000000

巴特西