TLE!!!
查看原帖
TLE!!!
377969
george0929楼主2023/1/22 18:35

RT. 50pts求助。。

#include<bits/stdc++.h>
using namespace std;
vector<int> V[400005];
int f[400005],arr[400005],vis[400005],ans[400005],cnt;
int fd(int x){
	if(f[x]==x){
		return x;
	}else{
		return fd(f[x]);
	}
}
void dfs(int x){
	for(int i=0;i<V[x].size();i++){
		int fx=fd(x),fy=fd(V[x][i]);
		if(vis[V[x][i]]||fx==fy){
			continue;
		}
		f[fx]=fy;
		cnt--;
		dfs(V[x][i]);
	}
	return;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		V[x].push_back(y);
		V[y].push_back(x);
	}
	int k;
	scanf("%d",&k);
	cnt=n-k;
	for(int i=1;i<=k;i++){
		scanf("%d",&arr[i]);
		vis[arr[i]]=1;
	}
	for(int i=0;i<n;i++){
		if(!vis[i]){
			dfs(i);
		}
	}
	int pos=0;
	ans[++pos]=cnt;
	for(int i=k;i>=1;i--){
		vis[arr[i]]=0;
		cnt++;
		dfs(arr[i]);
		ans[++pos]=cnt;
	}
	for(int i=pos;i>=1;i--){
		printf("%d\n",ans[i]);
	}
}

TLE on 5,6,7,8,10

2023/1/22 18:35
加载中...