提出 #66990892

---

ソースコード 拡げる

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){
	if(b==0) return 1;
	if(b==1) return a%p;
	int c=ksm(a,b/2,p);
	c=c*c%p;
	if(b%2==1) c=c*a%p;
	return c%p;	
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m,q;
int fa[300005],l[300005],r[300005],x[300005]; 
set<int> tu[300005];
int go(int x){
	if(x==fa[x]) return fa[x];
	return fa[x]=go(fa[x]);
}
signed main()
{
	//freopen("filename.in", "r", stdin);
	//freopen("filename.out", "w", stdout);
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		l[i]=read();
		r[i]=read();
		tu[l[i]].insert(r[i]);
		tu[r[i]].insert(l[i]);
	}
	q=read();
	for(int i=1;i<=q;i++){
		x[i]=read();
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	int ans=m;
	for(int i=1;i<=q;i++){
		int u=go(l[x[i]]);
		int v=go(r[x[i]]);
		if(u==v){
			cout<<ans<<'\n';
			continue;
		}
		if(tu[u].size()>tu[v].size()) swap(u,v);
		fa[u]=v;
		for(auto ed:tu[u]){
			if(tu[ed].count(u)){
				ans--;
				tu[ed].erase(u);
			}
			if(ed!=v&&tu[ed].count(v)==0){
				ans++;
				tu[ed].insert(v);
				tu[v].insert(ed);
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

提出情報

ジャッジ結果