P10777

考虑单个连通块，容易发现只要它不存在欧拉回路，就一定无解。

这是因为，如果一个连通块有若干个存在欧拉回路的子图，则它们一定呈环状。假设原图无欧拉回路，那么这些子图一定由一些链串联起来，这些链就导致原图一定是无解的。如果一个连通块连一个这样的子图都没有，那更不用说。

考虑多个连通块的情形，我们发现只要有一个连通块无解整个图就无解。否则，若连通块不是孤点（即存在黑边）贡献为

1

，反之为

0

。

于是，我们使用并查集维护连通块的黑边数量，并在此过程中顺便维护贡献。同时对于有解性判断，我们仅需记录每个节点的度数奇偶性，然后维护度数之和，只要为

0

就有解。

实现

CPP

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
int n,m,q,cnt,tot;
int d[N],fa[N],black[N];
struct EDGE{
	int u,v,c;
}e[N];

int fnd(int x){
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void mrg(int x,int y){
	x=fnd(x),y=fnd(y);
	if(x!=y)
		fa[x]=y;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	int ok=0;
	for(int i=1,u,v,c;i<=m;i++){
		cin>>u>>v>>c;
		e[++tot]={u,v,c};
		if(c){
			ok-=d[u]+d[v];
			d[u]^=1,d[v]^=1;
			ok+=d[u]+d[v];
		}
		mrg(u,v);
	}
	for(int i=1;i<=m;i++){
		if(e[i].c){
			int u=fnd(e[i].u);
			if(!black[u])
				cnt++;
			black[u]++;
		}
	}
	cin>>q;
	while(q--){
		int op,x;
		cin>>op;
		if(op==1){
			cin>>x,x++;
			ok-=d[e[x].u]+d[e[x].v];
			d[e[x].u]^=1,d[e[x].v]^=1;
			ok+=d[e[x].u]+d[e[x].v];
			if(e[x].c){
				e[x].c=0;
				black[fnd(e[x].u)]--;
				if(!black[fnd(e[x].u)])
					cnt--;
			}
			else{
				e[x].c=1;
				if(!black[fnd(e[x].u)])
					cnt++;
				black[fnd(e[x].u)]++;
			}
		}
		else
			cout<<(ok?-1:cnt)<<'\n';
	}
	return 0;
}

文章操作

相关推荐

评论

P10777