FZU2259 : 图

FZU2259 : 图

假设删除的边是 (u,v)，分两种情况讨论：

1.删除 (u,v)之后 (u,v)不再连通，那么说明 (u,v)是图的桥，同时整个图都要是二分图。

2.删除 (u,v)之后 (u,v)依然连通，那么图不能是二分图，但是删除 (u,v)之后必须要是二分图，这说明 (u,v)位于所有奇环的交上，在忽略这条边之后可以进行黑白染色，且 u,v必定同色。对图求出dfs生成树，找出所有基环，对每条边标记它被多少个奇数长度的基环与多少个偶数长度的基环经过。如果一条边被所有奇数长度的基环经过，且不被任何一个偶数长度的基环经过，那么就可行。

时间复杂度 O(n+m)。

#include<cstdio>
const int N=200010;
int n,m,i,x,y,dep[N],g[N],v[N<<1],w[N<<1],nxt[N<<1],ed,d[N],dfn,f[N];
int cnt,loop,tag0[N],tag1[N],h0[N],h1[N],ans;
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){d[x]=++dfn;for(int i=g[x];i;i=nxt[i])if(w[i]!=f[x]){int y=v[i];if(d[y]&&d[y]<=d[x]){if(dep[x]^dep[y]){tag0[y]--;tag0[x]++;h0[w[i]]=1;}else{if(x==y)loop++;else cnt++;tag1[y]--;tag1[x]++;h1[w[i]]=1;}}else if(!d[y])f[y]=w[i],dep[y]=dep[x]^1,dfs(y);}
}
void cal(int x){for(int i=g[x];i;i=nxt[i])if(f[v[i]]==w[i]&&d[v[i]]>d[x])cal(v[i]),tag0[x]+=tag0[v[i]],tag1[x]+=tag1[v[i]];h0[f[x]]=tag0[x],h1[f[x]]=tag1[x];
}
namespace BCC{
int cut[N],g[N],v[N<<1],nxt[N<<1],ed;
int f[N],dfn[N],low[N],num;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void tarjan(int x){dfn[x]=low[x]=++num;for(int i=g[x];i;i=nxt[i])if(!dfn[v[i]]){f[v[i]]=i>>1,tarjan(v[i]);if(low[x]>low[v[i]])low[x]=low[v[i]];}else if(f[x]!=(i>>1)&&low[x]>dfn[v[i]])low[x]=dfn[v[i]];if(f[x]&&low[x]==dfn[x])cut[f[x]]=1;
}
}
int main(){while(~scanf("%d%d",&n,&m)){for(BCC::ed=i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y,i),add(y,x,i);BCC::add(x,y),BCC::add(y,x);}for(i=1;i<=n;i++)if(!d[i])dfs(i),cal(i);cnt+=loop/2;if(!cnt){for(i=1;i<=n;i++)if(!BCC::dfn[i])BCC::tarjan(i);for(i=1;i<=m;i++)if(BCC::cut[i])ans++;}else{for(i=1;i<=m;i++)if(h1[i]==cnt&&!h0[i])ans++;}printf("%d\n",ans);ed=dfn=cnt=loop=ans=0;for(i=0;i<=n;i++)dep[i]=g[i]=d[i]=f[i]=tag0[i]=tag1[i]=0;for(i=0;i<=m;i++)h0[i]=h1[i]=0;for(i=0;i<=m;i++)BCC::cut[i]=0;for(i=0;i<=n;i++)BCC::g[i]=BCC::f[i]=BCC::dfn[i]=BCC::low[i]=0;BCC::num=0;}
}