60pts wa找不到问题

P1197 [JSOI2008] 星球大战

Yannik @ 2024-09-26 19:47:51

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5+10;
int T,n,m,k;
int x[N],y[N],z[N];
int ans[N];
map<int,int> mp;
vector<int> g[N];
struct dsu{
    vector<int> f;
    dsu(int n):f(n){
        iota(f.begin(),f.end(),0);
    }
    int find(int x){
        return f[x]==x?x:f[x]=find(f[x]);
    }
    bool merge(int a,int b){
        int fa=find(a),fb=find(b);
        if(fa==fb) return false;
        f[fb]=fa;
        return true;
    }
    bool same(int a,int b){
        return find(a)==find(b);
    }
};
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    dsu ds(n+1);
    for(int i=1;i<=m;i++){
        cin>>x[i]>>y[i];
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>z[i];
        mp[z[i]]=1;
    }
    ans[k+1]=n;
    for(int i=1;i<=m;i++){
        if(!mp[x[i]]&&!mp[y[i]]){
            ds.merge(x[i],y[i]);
            ans[k+1]--;
        }
    }
    for(int i=k;i>=1;i--){
        ans[i]=ans[i+1]; 
        mp[z[i]]=0;
        for(auto t:g[z[i]]){
            if(!ds.same(t,z[i])&&!mp[t]){
                ans[i]--;
                ds.merge(t,z[i]);
            }
        }
    }
    for(int i=1;i<=k+1;i++){
        cout<<ans[i]-i+1<<"\n"; 
    }
    return 0;
} 

|