为什么将ruin数组改成int就能过样例
查看原帖
为什么将ruin数组改成int就能过样例
229373
Xeqwq楼主2022/8/8 20:31

rt. 但是只有20分 而ruin数组用bool连样例都过不了

#include <iostream>
#include <vector>
using namespace std;
int n,m,k;
const int Maxn=100005;
int fa[Maxn];
int find(int x)
{
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void merge(int x,int y)
{
	fa[find(x)]=find(y);
}
vector<int> adj[Maxn];
int ord[Maxn];
int ruin[Maxn],ans[Maxn];
int f[Maxn];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++) fa[i]=i;
	int u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&ord[i]);
		ruin[ord[i]]=1;
	}
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(ruin[i]) continue;
		for(int j=0;j<adj[i].size();j++)
		{
			if(!ruin[adj[i][j]])
				merge(adj[i][j],i);
		}
	}
	for(int i=0;i<n;i++)
	{
		if(ruin[i]) continue;
		if(!f[i])
		{
			f[i]=1;
			cnt++;
		}
	}
	ans[k+1]=cnt;
	for(int i=k;i>=1;i--)
	{
		ruin[ord[i]]=0;
		cnt++;
		for(int j=0;j<adj[ord[i]].size();j++)
		{
			if(!ruin[adj[ord[i]][j]])
			{
				if(find(ord[i])!=find(adj[ord[i]][j]))
				{
					cnt--;
				}
				merge(ord[i],adj[ord[i]][j]);
			}
		}
		ans[i]=cnt;
	}
	for(int i=1;i<=k+1;i++)
		printf("%d\n",ans[i]);
}
2022/8/8 20:31
加载中...