BZOJ4424/CF19E Fairy（dfs树+树上差分）-白红宇

BZOJ4424/CF19E Fairy（dfs树+树上差分）

阅读量：5263 次

发布时间：2019-06-14

本文共 2019 字，大约阅读时间需要 6 分钟。

　　即删除一条边使图中不存在奇环。如果本身就是个二分图当然任意一条边都可以，先check一下。否则肯定要删除在所有奇环的交上的边。

　　考虑怎么找这些边。跑一遍dfs造出dfs树，找出返祖边构成的奇环。可以通过树上差分标记奇环上的边。

　　但是这显然只包含了一部分奇环。注意到如果某条在奇环上的边同时也在一个偶环上，一定可以找到一个不包含这条边的奇环。并且图中所有其他奇环都是由所找到的奇环加上偶环得到的，所以这就是充分的了。

　　数据中有重边自环，自环特判一下比较舒服，而任意一条重边都不可能在答案中（本身就是二分图除外）。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 1000010map
             
               f[N];int n,m,p[N],t=-1,fa[N<<1],deep[N],cnt[2][N<<1],delta[2][N],tot;struct data{ int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]);}void dfs(int k,int from){ for (int i=p[k];~i;i=edge[i].nxt) if (edge[i].to!=from) if (deep[edge[i].to]&&deep[edge[i].to]<=deep[k]) { int op=deep[k]-deep[edge[i].to]&1; tot+=op^1;cnt[op][i]++; delta[op][k]++,delta[op][edge[i].to]--; } else if (!deep[edge[i].to]) { deep[edge[i].to]=deep[k]+1; dfs(edge[i].to,k); }}int Count(int op,int k,int from){ int s=0; for (int i=p[k];~i;i=edge[i].nxt) if (edge[i].to!=from&&!deep[edge[i].to]) { deep[edge[i].to]=deep[k]+1; int d=Count(op,edge[i].to,k); s+=d,cnt[op][i]+=d; } s+=delta[op][k]; return s;}int main(){#ifndef ONLINE_JUDGE freopen("bzoj4424.in","r",stdin); freopen("bzoj4424.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(); for (int i=1;i<=n*2;i++) fa[i]=i; memset(p,255,sizeof(p)); bool flag=1;int sc=0; for (int i=1;i<=m;i++) { int x=read(),y=read(); if (x!=y) { f[x][y]++,f[y][x]++; addedge(x,y);if (x!=y) addedge(y,x); fa[find(x)]=find(y+n),fa[find(x+n)]=find(y); if (find(x)==find(y)) flag=0; } else sc=sc?m+1:i; } if (sc) { if (!flag||sc>m) {cout<<0;return 0;} cout<<1<
              
               <

转载于:https://www.cnblogs.com/Gloid/p/9872454.html

你可能感兴趣的文章