[BZOJ3706]反色刷（并查集+欧拉图）

题目描述

传送门

题目大意：给出一个n个点m条边的无向图，每一条边有一个颜色0/1，每一次可以选择一个环（不一定是简单环）使环上的所有边都反色。问最少选择多少次使所有的边都变成白色。这个图的边的颜色会发生变化，每一次操作有可能使一条边反色。

题解

欧拉回路，比较显然的一点是有解的充要条件是没有奇点 刚开始一直在往维护黑边的连通块个数的方面考虑，然后就一直在想什么写个lct啊… 但实际上这样做是有一点问题的，因为白边不一定不走只要走偶数次就可以 那么可以将一条白边看成两条黑边，这样的话对每个点的奇偶性是没有影响的，而且同样是求欧拉回路 用并查集先维护出连通块了之后，只需要记录一下每一个连通块是否有黑边，如果有黑边的话就需要刷一次，没有黑边的话就不需要，无解的话同样用度数的奇偶性判断

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 1000005 int n,m,q,ans,du[N],f[N],size[N],cnt[2]; struct data{int x,y,z;}e[N]; int find(int x) { if (x==f[x]) return x; f[x]=find(f[x]); return f[x]; } void merge(int x,int y) { int f1=find(x),f2=find(y); if (f1!=f2) f[f1]=f2; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) f[i]=i; for (int i=1;i<=m;++i) { int x,y,z;scanf("%d%d%d",&x,&y,&z); if (!z) du[x]+=2,du[y]+=2; else ++du[x],++du[y]; merge(x,y); e[i].x=x,e[i].y=y,e[i].z=z; } for (int i=1;i<=n;++i) ++cnt[du[i]&1]; for (int i=1;i<=m;++i) { int x=e[i].x,y=e[i].y,z=e[i].z; int fa=find(x); if (z) { if (!size[fa]) ++ans; ++size[fa]; } } scanf("%d",&q); while (q--) { int opt;scanf("%d",&opt); if (opt==1) { int id;scanf("%d",&id);++id; int x=e[id].x,y=e[id].y,z=e[id].z; int fa=find(x); if (!z) { --cnt[du[x]&1],--cnt[du[y]&1],--du[x],--du[y],++cnt[du[x]&1],++cnt[du[y]&1]; if (!size[fa]) ++ans; ++size[fa]; } else { --cnt[du[x]&1],--cnt[du[y]&1],++du[x],++du[y],++cnt[du[x]&1],++cnt[du[y]&1]; --size[fa]; if (!size[fa]) --ans; } e[id].z^=1; } else { if (cnt[1]) puts("-1"); else printf("%d\n",ans); } } }