bzoj4238 电压

　　首先先直接对图进行二染色，dfs染完色后，有的边为搜索树边，有的为非树边，当非树边连接的两头的点为异色的时候，那么很明显这条非树边和树边构成的环上的边必然不可能成为答案；如果非树边的两端的点同色，那么所有这种类型的非树边与树边构成的环的交集就是答案，对于一条这样的非树边，如果要使其变成二分图的合法边，那么必然会在其与树边构成的环中剔除掉一条边，这样树变成了两个部分，把其中一部分反色，在连上这条非树边，也是一个合法二分图，那么所有这种类型的边构成的环的交集，就是答案的可选集。

　　代码

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define N 500010

 using namespace std;

 int n,m,i,a[N],b[N],dp,p[N],pre[N],tt[N],id[N],vis[N],treeEdge[N];

 int deep[N],color[N],fa[N],sum[N],cnt,value[N];

 int s[N][];

 void link(int x,int y,int z)

 {

     dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y;id[dp]=z;

 }

 void dfs(int x)

 {

     int i;

     vis[x]=;

     i=p[x];

     while (i)

     {

         if (!vis[tt[i]])

         {

             deep[tt[i]]=deep[x]+;

             treeEdge[id[i]]=;

             color[tt[i]]=-color[x];

             fa[tt[i]]=x;

             dfs(tt[i]);

         }

         i=pre[i];

     }

 }

 void gao(int x)

 {

     int i,tmp=;

     vis[x]=;

     i=p[x];

     while (i)

     {

         if (!vis[tt[i]])

         {

             gao(tt[i]);

             tmp+=sum[tt[i]];

             value[id[i]]=sum[tt[i]];

         }

         i=pre[i];

     }

     sum[x]+=tmp;

 }

 int lca(int x,int y)

 {

     if(deep[x]>deep[y])x^=y^=x^=y;

     int i;

     for(i=;i>=;i--)

     {

         if(deep[y]-deep[x]>=(<<i))

         {

             y=s[y][i];

         }

     }

     if(x==y)return x;

     for(i=;i>=;i--)

     {

         if(s[x][i]!=s[y][i])

         {

             x=s[x][i];

             y=s[y][i];

         }

     }

     return fa[x];

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (i=;i<=m;i++)

     {

         scanf("%d%d",&a[i],&b[i]);

         link(a[i],b[i],i);

         link(b[i],a[i],i);

     }

     for (i=;i<=n;i++) if (!vis[i]) dfs(i);

     for(i=;i<=n;i++)s[i][]=fa[i];

     for(int h=;h<;h++)

     {

         for(i=;i<=n;i++)

         {

             s[i][h]=s[s[i][h-]][h-];

         }

     }

     for (i=;i<=m;i++)

     if ((!treeEdge[i])&&(color[a[i]]!=color[b[i]]))

     {

         sum[a[i]]--;

         sum[b[i]]--;

         sum[lca(a[i],b[i])]+=;

     }

     for (i=;i<=m;i++)

     if ((!treeEdge[i])&&(color[a[i]]==color[b[i]]))

     {

         cnt++;

         sum[a[i]]++;

         sum[b[i]]++;

         sum[lca(a[i],b[i])]-=;

     }

     memset(vis,,sizeof(vis));

     for (i=;i<=n;i++)

     if (!vis[i]) gao(i);

     int ans=;

     for (i=;i<=m;i++)

     if ((treeEdge[i])&&(value[i]==cnt)) ans++;

     if (cnt==) ans++;

     printf("%d\n",ans);

 }