【两关】求调

0 pts

#include<bits/stdc++.h>
#define int long long
#define f1(i,n,m) for(int i=n;i<=m;i++)
#define f2(i,n,m) for(int i=n;i>=m;i--)
using namespace std;
const int maxn=4e5+5;
int n,m,x[maxn],y[maxn],fa[maxn],a[maxn],vis[maxn],ans[maxn],k;
vector<int>vt[maxn];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int uniSet(int x,int y){
    x=find(x);y=find(y);
    if(x!=y){
        fa[y]=x;
    }
}
signed main(){
    cin>>n>>m;
    f1(i,1,n) fa[i]=i;
    f1(i,1,m){
        cin>>x[i]>>y[i];
        x[i]++;
        y[i]++;
        vt[x[i]].push_back(y[i]);
        vt[y[i]].push_back(x[i]);
    }
    cin>>k;
    f1(i,1,k){
        cin>>a[i];
        a[i]++;
        vis[a[i]]=1;
    } 
    int cnt=n-k;
    f1(i,1,m){
        if(vis[x[i]]==0&&vis[y[i]]==0&&find(x[i])!=find(y[i])){
            uniSet(x[i],y[i]);
            cnt--;
        }
    }
    ans[k]=cnt;
    f2(iii,k,1){
        vis[a[iii]]=0;
        cnt++;
        f1(i,0,vt[a[iii]].size()-1){
            int v=vt[a[iii]][i];
            if(vis[v]==0&&find(a[iii])!=find(v)){
                uniSet(a[iii],v);
                cnt--;
            }
        }
        a[iii-1]=cnt;
    }
    f1(i,0,k) cout<<ans[i]<<"\n";
    return 0;
}