萌新40分玄学TLE求救
查看原帖
萌新40分玄学TLE求救
174987
Nintendo__switch楼主2021/2/23 08:47

加了并查集和读入优化,但还是T了四个点,求大佬帮忙看一眼QWQ

代码如下:

#include<bits/stdc++.h>
using namespace std;
int fa[400100],head[400100],z[400100],ans,bui[400100];
bool vis[400100];
int find(int a)
{
	int b=a,c;
	while(a!=fa[a])
		a=fa[a];
	while(b!=a)
	{
		c=b;
		b=fa[b];
		fa[c]=a;
	}	
}
struct o
{
	int to,next,from;
}a[400100];
int ii;
void add(int x,int y)
{
	a[++ii].to=y;
	a[ii].from=x;
	a[ii].next=head[x];
	head[x]=ii;
}
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
int main()
{
	int n,m;
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		head[i]=-1;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		x=read(),y=read();
		add(x,y);
		add(y,x); 
	}
	int kk;
	kk=read();
	ans=n-kk;
	for(int i=1;i<=kk;i++)
	{
		int k;
		k=read();
		vis[k]=1;
		z[i]=k;
	}
	for(int i=1;i<=2*m;i++)
	{
		if(vis[a[i].from]==0&&vis[a[i].to]==0)
		{
			int oo=find(a[i].from),pp=find(a[i].to);
			if(oo!=pp)
			{
				fa[pp]=oo;
				ans--;
			}
		}
	}
	bui[kk+1]=ans;
	for(int i=kk;i>=1;i--)
	{
		int o=z[i];
		vis[o]=0;
		ans++;
		for(int j=head[o];j!=-1;j=a[j].next)
		{
			int oo=find(a[j].to),pp=find(o);
			int df=fa[oo],gh=fa[pp];
			if(vis[a[j].to]==0&&df!=gh)
			{
				ans--;
				fa[oo]=fa[pp];
			}
		}
		bui[i]=ans;
	}
	for(int i=1;i<=kk+1;i++)
		cout<<bui[i]<<endl;
	return 0;
}
2021/2/23 08:47
加载中...