P10777

KidA · 2025-10-05 15:50:58 · 题解

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

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

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

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

:::success[实现]

#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;
}

:::