求助,玄关

P1197 [JSOI2008] 星球大战

CheZiHe929 @ 2024-01-28 17:01:56

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=4e5+5;

int n,m,k,x[MAXN],y[MAXN],kkk[MAXN];
bool f[MAXN];//1 shan
int ans[MAXN],num;
int fa[MAXN];
std::vector<int> v[MAXN];

void add(int s,int e){v[s].push_back(e);v[e].push_back(s);}
void init(){for(int i=1;i<=n;i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){int fx=find(x),fy=find(y);if(fx!=fy){num--;fa[fy]=fx;}}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    init();

    std::cin>>n>>m;
    for(int i=1;i<=m;i++){
        std::cin>>x[i]>>y[i];
        add(x[i],y[i]);
    }

    std::cin>>k;
    for(int i=1;i<=k;i++)std::cin>>kkk[i],f[kkk[i]]=1;

    num=n-k;
    for(int i=1;i<=m;i++)
        if(!f[x[i]]&&!f[y[i]])merge(x[i],y[i]);

    ans[k+1]=num;
    for(int i=k;i>=1;i--){
        int x=kkk[i];
        num++;
        f[x]=0;
        for(int j=0;j<v[x].size();j++)
            if(!f[v[x][j]])merge(x,v[x][j]);

        ans[i]=num;
    }

//  for(int i=0;i<n;i++)std::cout<<fa[i]<<" \n"[i==n-1];
//      for(int j=0;j<v[i].size();j++)
//          std::cout<<v[i][j]<<" \n"[j==v[i].size()-1];

    for(int i=1;i<=k+1;i++)std::cout<<ans[i]<<endl;

    return 0;
}

by CheZiHe929 @ 2024-01-28 18:02:13

此贴结,楼主在没输入 n 之前就初始化/cf/cf/cf


|