蒟蒻RE 90pt 求助大佬

P1197 [JSOI2008] 星球大战

Victor08 @ 2024-09-08 23:54:08

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[200005],q[200005],ans,f[200005],answ[200005];
vector<int> p[200005];
void build(){
    for(int i=0;i<n;i++){
        f[i]=i;
    }
}
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void add(int x){
    for(int i=0;i<p[x].size();i++){
        if(!a[p[x][i]]){
            if(find(x)!=find(p[x][i])){
                ans--;
                f[find(p[x][i])]=f[x];
            }
        }
    }
}
int main(){
    cin>>n>>m;
    build();
    while(m--){
        int u,v;
        cin>>u>>v;
        p[u].push_back(v);
        p[v].push_back(u);
    }
    cin>>k;
    for(int i=k;i>=1;i--){
        int x;
        cin>>x;
        a[x]=1;//被拿下
        q[i]=x;//顺序
    }
    ans=n-k;
    for(int i=0;i<n;i++){
        if(!a[i]){
            add(i);
        }
    }
    answ[0]=ans;
    for(int i=1;i<=k;i++){
        ans++;
        a[q[i]]=0;
        add(q[i]);
        answ[i]=ans;
    }
    for(int i=k;i>=0;i--){
        cout<<answ[i]<<endl;
    }
    return 0;
}

by False0099 @ 2024-09-14 11:22:28

他题目里面给的是M的范围,然后N的范围最大可以是2M,所以你要初始化为两倍


by Victor08 @ 2024-09-19 23:49:59

确实,初始化为两倍就过了 谢谢!


|