理论上时间复杂度能过,TLE求助
查看原帖
理论上时间复杂度能过,TLE求助
370648
柠檬布丁吖楼主2023/2/17 20:22
//Closin
#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int ret=0,f=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-f;
    for(;c>='0'&&c<='9';c=getchar()) ret=ret*10+c-'0';
    return ret*f;
}

const int maxn=2e5+55;
int N,M;
int head[maxn],tot;
struct cow{
	int ne;
	int to;
	int w;
}c[maxn];

void add(int x,int y){
	c[++tot].w=x;
	c[tot].to=y;
	c[tot].ne=head[x];
	head[x]=tot;
}

int r[maxn],fa[maxn],ans[maxn];
bool vis[maxn];

void init(){
	for(int i=1;i<=N;i++){
		fa[i]=i;
	}
}

int _find(int x){
	if(fa[x]==x) return x;
	else fa[x]=_find(fa[x]);
}

signed main(void){
	
	N=read();M=read();
	
	for(int i=1;i<=M;i++){
		int u,v;
		u=read();v=read();
		add(u,v);add(v,u);
	}
	
	for(int i=1;i<=N;i++){
		r[i]=read();	
	}
	
	init();
	vis[r[N]]=true;
	ans[N]=1;
	int k=0;
	for(int i=N-1;i>=1;i--){
		vis[r[i]]=true;
		for(int j=head[r[i]];j;j=c[j].ne){
			if(vis[c[j].to]==1){
				int _x=_find(r[i]),_y=_find(c[j].to);
				if(_x!=_y){
					++k;
					fa[_x]=_y;
				}
			}
			
//			puts("awa");
		}
		
		if(k==N-i) ans[i]=1;
		else ans[i]=0;
	}
	
	for(int i=1;i<=N;i++){
		if(ans[i]==1) printf("YES\n");
		else printf("NO\n");
	}
	
	return 0;
}
2023/2/17 20:22
加载中...