社区讨论

萌新求救 玄学错误

学术版参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi7wfnhh
此快照首次捕获于
2025/11/21 04:43
4 个月前
此快照最后确认于
2025/11/21 04:43
4 个月前
查看原帖
先谢谢进来的dalao们
CPP
#include<cstdio>
using namespace std;
const int MN=400002;
int st[MN],h[MN],fa[MN],ans[MN],n,m,tot,k,cnt;
bool bz[MN];
int find(int z){
	if(fa[z]==z)
		return z;
	return fa[z]=find(fa[z]);
}
struct edge{
	int now;
	int to;
	int last;
}e[MN];
void add(int a,int b){
	e[++cnt].to=b;
	e[cnt].now=a;
	e[cnt].last=st[a];
	st[a]=cnt;
}
int main(){
	int u,l,x,y;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;++i){
		fa[i]=i;
		st[i]=-1;
	}
	for(int i=0;i<m;++i){
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
	scanf("%d",&k);
	tot=n-k;
	for(int i=1;i<=k;i++){
		scanf("%d",&l);
		bz[l]==true;
		h[i]=l;
	}
	for(int i=0;i<m*2;i++){
		if(bz[e[i].now]==false&&bz[e[i].to]==false){
			if(find(e[i].now)!=find(e[i].to)){
				tot--;
				fa[find(e[i].now)]=fa[find(e[i].to)];
			}
		}
	}
	ans[k+1]=tot;
	for(int i=k;i>=1;i--){
		u=h[i];
		tot++;
		bz[u]=false;
		for(int j=st[u];j;j=e[j].last){
			if(bz[e[j].to]==false&&fa[find(u)]!=fa[find(e[j].to)]){
				tot--;
				fa[find(e[i].to)]=fa[find(u)];
			}
		}
		ans[i]=tot;
	}
	for(int i=1;i<=k+1;++i)
		printf("%d\n",ans[i]);
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...