40分求助!

P1197 [JSOI2008] 星球大战

Cure_Wing @ 2023-02-01 14:09:49

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using std::cin;using std::cout;
constexpr int M=200005;
int n,m,x[M],y[M],k,a[M<<1],fa[M<<1],ans[M<<1];
bool vis[M<<1];
std::vector<int>edge[M<<1];
inline int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
inline bool add(int u,int v){
    int fu=find(u),fv=find(v);
    if(fu==fv) return 0;
    fa[fv]=fu;
    return 1;
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>x[i]>>y[i];
        ++x[i];++y[i];
        edge[x[i]].push_back(y[i]);
        edge[y[i]].push_back(x[i]);
    }
    cin>>k;
    for(int i=1;i<=k;++i){
        cin>>a[i];
        ++a[i];
        vis[a[i]]=1;
    }
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i)
        if(!vis[x[i]]&&!vis[y[i]])
            add(x[i],y[i]);
    for(int i=1;i<=n;++i) ans[k]+=(fa[i]==i)&&(!vis[a[i]]);
    for(int i=k;i>=1;--i){
        ans[i-1]=ans[i]+1;
        for(auto j:edge[a[i]])
            if(!vis[j])
                ans[i-1]-=add(j,a[i]);
        vis[a[i]]=0;
    }
    for(int i=0;i<=k;++i) cout<<ans[i]<<'\n';
    return 0;
}

by Cure_Wing @ 2023-02-01 16:19:18

for(int i=1;i<=n;++i) ans[k]+=(fa[i]==i)&&(!vis[i]);
此贴完结。


|