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

Sample Output

HINT

100%  n,m,q <= 1000000, c < 2，沒有重邊自環

Source

題解：歐拉圖+并查集

剛開始想的是因為是反色刷，所以刷過的邊不能是白色的邊，否則又出現了黑色的邊。那么就是要求只利用黑邊，所形成的圖的連通塊的個數，發現根本不可做。

因為這根本就是不對的，因為如果剛開始是白邊，那么刷兩次就可以讓他仍然是白邊。所以反色刷是有可能刷過白邊的。

那么什么情況是無解的呢？就是存在點只考慮黑邊的度不是偶數。

為什么呢？因為你要回到起點，并且使所有連通的黑邊都被粉刷一次。如果說刷過的路徑全是黑邊的話，那么就是說圖中存在歐拉路徑，那么歐拉路徑存在的條件就是所有點的度都是偶數。

那么我們如何考慮白邊呢？可以發現白邊的作用就是連接兩個全黑的連通塊。而且只要幾個全黑的連通塊連通，一定存在方案使他們可以一次刷下來。

那么最后的答案其實就是含黑邊的連通塊個數。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 1000003using namespace std;int fa[N],sum[N],ans,cnt,n,m;int x[N],y[N],c[N],du[N];int find(int x){	if (fa[x]==x) return x;	fa[x]=find(fa[x]);	return fa[x];}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&m);	for (int i=1;i<=n;i++) fa[i]=i;	for (int i=1;i<=m;i++) {		scanf("%d%d%d",&x[i],&y[i],&c[i]);		int r1=find(x[i]); int r2=find(y[i]);		if (r1!=r2) {			if (sum[r1]&&sum[r2]) ans--;			sum[r1]+=sum[r2]; fa[r2]=r1;		}		if (c[i]) {			sum[r1]++; if (sum[r1]==1) ans++;			du[x[i]]++; du[y[i]]++;			if (du[x[i]]&1) cnt++;			else cnt--;			if (du[y[i]]&1) cnt++;			else cnt--; 		}	}	int q; scanf("%d",&q);	for (int i=1;i<=q;i++) {		int opt,now;		scanf("%d",&opt);		if (opt==1) {			scanf("%d",&now); now++;			int r1=find(x[now]);			c[now]^=1;			if (c[now]) {//變成黑邊 				sum[r1]++; if (sum[r1]==1) ans++;				du[x[now]]++; du[y[now]]++;			    if (du[x[now]]&1) cnt++;			    else cnt--;			    if (du[y[now]]&1) cnt++;			    else cnt--; 			}			else {				sum[r1]--; if (sum[r1]==0) ans--;				du[x[now]]--; du[y[now]]--;			    if (du[x[now]]&1) cnt++;			    else cnt--;			    if (du[y[now]]&1) cnt++;			    else cnt--; 			}		}		else {			if (cnt) PRintf("-1/n");			else printf("%d/n",ans);		}	}}