标签：欧拉图，并查集
Description
给一张无向图，边有黑白两种颜色，现在你有一堆反色刷，可以从任意点开始刷，经过若干条边后回到起点。
现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。
因为某种原因，边的颜色是会改变的，于是。。
需要支持以下操作：
1 x 把第x条边反色（编号从0~m-1）
2 询问当前图中最少需要多少个反色刷
Input
第一行两个整数n m表示这张图有n个点m条边
接下来m行 每行3个整数 u v c表示一条无向边和这条边的颜色(0为白色 1为黑色)
接下来一个整数q 表示有q个操作
接下来q行为操作 描述如上
Output
对于每个询问 输出一行一个整数
表示最少需要的反色刷个数 如果没有合法方案输出-1
Sample Input
6 6
1 2 1
2 3 1
1 3 1
4 5 1
5 6 1
4 6 1
14
2
1 0
2
1 1
1 2
2
1 3
1 4
1 5
2
1 3
1 4
1 5
2
Sample Output
2
-1
1
0
1
HINT
100% n,m,q <= 1000000, c < 2，没有重边自环
分析：如果存在一点黑边度数为奇数，那么肯定无解，输出-1，如果有解的话，统计下有多少个含有黑边的联通子块就可以了，用并查集维护，否则可能会TLE
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
#define reg(x) for(int i=head[x];i;i=e[i].next)
using namespace std;
inline LL read()
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
LL n,m,q,ans,cnt=0,r1,r2,x,y;
LL fa[maxn],u[maxn],v[maxn],c[maxn],d[maxn],sum[maxn];
inline LL find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
n=read(),m=read();
rep(i,1,n)fa[i]=i;
rep(i,1,m){
u[i]=read(),v[i]=read(),c[i]=read();
r1=find(u[i]),r2=find(v[i]);
if(r1!=r2){
fa[r1]=r2;
if(sum[r2]&&sum[r1])ans--;
sum[r2]+=sum[r1];
}
if(c[i]){
sum[r2]++;
if(sum[r2]==1)ans++;
d[u[i]]++,d[v[i]]++;
if(d[u[i]]&1)cnt++;else cnt--;
if(d[v[i]]&1)cnt++;else cnt--;
}
else if(r1!=r2&&sum[r1]&&sum[r2])ans--;
}
q=read();
rep(i,1,q){
x=read();
if(x==1){
y=read();y++;
c[y]^=1;r1=find(u[y]);
if(c[y]){
sum[r1]++;
if(sum[r1]==1)ans++;
d[u[y]]++,d[v[y]]++;
if(d[u[y]]&1)cnt++;else cnt--;
if(d[v[y]]&1)cnt++;else cnt--;
}
else{
sum[r1]--;if(sum[r1]==0)ans--;
d[u[y]]--,d[v[y]]--;
if(d[u[y]]&1)cnt++;else cnt--;
if(d[v[y]]&1)cnt++;else cnt--;
}
}
else{
if(cnt)cout<<"-1\n";
else printf("%lld\n",ans);
}
}
return 0;
}
