题目概述

CF19E数据加大版。

解题报告

不能分治+LCT啦。由于只删除一条边所以可以大力分类讨论。先用DFS树+差分求出树边被多少个奇环覆盖以及被多少个偶环覆盖，然后：

1. 树边：如果处于所有奇环之间，并且不被偶环覆盖那么删除之后所有奇环都消失了。
2. 非树边：如果是奇环，并且只有这一个奇环那么删除之后就可行。

注意下自环和重边就好了。

示例程序

ps:这个程序在只有偶环没有奇环的时候跪了，BZOJ数据渣的一批过了，我不想改了Orz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000,maxm=2000000;

int n,m,num[maxn+5][2],dep[maxn+5],tot,ans;bool us[maxn+5],vis[maxm+5];
int E,lnk[maxn+5],nxt[(maxm<<1)+5],son[(maxm<<1)+5];

#define Add(x,y) (son[E]=(y),nxt[E]=lnk[x],lnk[x]=E++)
void Dfs(int x,int pre=-1){
    for (int j=lnk[x];~j;j=nxt[j])
        if ((j^1)!=pre){
            if (son[j]==x) {tot+=!us[j>>1];us[j>>1]=true;continue;}if (!dep[son[j]]) dep[son[j]]=dep[x]+1,Dfs(son[j],j);
            if (dep[x]>dep[son[j]]) {us[j>>1]=true;int c=dep[x]-dep[son[j]]+1&1;tot+=c;num[x][c]++;num[son[j]][c]--;}
        }
}
void getnum(int x,int pre=-1){
    for (int j=lnk[x];~j;j=nxt[j])
        if ((j^1)!=pre&&!us[j>>1]) getnum(son[j],j),num[x][0]+=num[son[j]][0],num[x][1]+=num[son[j]][1];
}
void getans(int x,int pre=-1){
    for (int j=lnk[x];~j;j=nxt[j])
        if ((j^1)!=pre)
            if (us[j>>1]) vis[j>>1]=(dep[x]-dep[son[j]]+1&1)&&tot==1;
            else vis[j>>1]=num[son[j]][1]==tot&&!num[son[j]][0],getans(son[j],j);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);E=0;memset(lnk,255,sizeof(lnk));
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    for (int i=1;i<=n;i++) if (!dep[i]) dep[i]=1,Dfs(i),getnum(i);
    for (int i=1;i<=n;i++) if (dep[i]==1) getans(i);for (int i=0;i<m;i++) ans+=vis[i];printf("%d\n",ans);
    for (int i=0,fr=true;i<m;i++) if (vis[i]) {fr?fr=false:putchar(' ');printf("%d",i+1);};return puts(""),0;
}