MnZn在线求助冰茶寄
查看原帖
MnZn在线求助冰茶寄
404469
LJN1117楼主2024/10/22 21:04

WA on 2,3,4,5,6,7,8,9,10

已调0.5h,请求支援

#include<bits/stdc++.h>
#define int long long
#define maxn 200100

using namespace std;

int n,m;
int used[maxn],q[maxn],fa[maxn],ans[maxn];
int head[maxn],nxt[maxn<<1],to[maxn<<1],tot;

void add(int x,int y){
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}

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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++) cin>>q[i];
    int sum=0;
    for(int i=n;i>=1;i--){
        sum++;
        used[q[i]]=1;
        for(int j=head[q[i]];j;j=nxt[j]){
            int y=to[j];
            if(find(q[i])!=find(y)) fa[find(y)]=find(q[i]);
            if(used[y]) sum--;
        }
        if(sum==1) ans[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(ans[i]==1) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
2024/10/22 21:04
加载中...