Luogu

BZOJ

分析

倒着做，用并查集维护联通即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000;

struct Edge { int v,nxt; };
Edge e[MAXN];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int root[MAXN];
inline void init(int n) { for (re int i=1;i<=n;++i) root[i]=i; }
inline int find(int x) { return x==root[x]?x:root[x]=find(root[x]); }
inline void merge(int a,int b) { a=find(a),b=find(b); if (a!=b) root[a]=b; }
inline int check(int a,int b) { return find(a)==find(b); }

int Ans[MAXN];
int d[MAXN],killed[MAXN];

int main() {
    int n=read(),m=read(); init(n+10);
    for (re int i=1;i<=m;++i) {
        int u=read()+1,v=read()+1;
        addEdge(u,v); addEdge(v,u);
    }
    int k=read();
    for (re int i=1;i<=k;++i) {
        d[i]=read()+1;
        killed[d[i]]=1;
    }
    for (re int u=1;u<=n;++u) {
        if (killed[u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (!killed[v]) merge(u,v);
        }
    }
    int ans=0;
    for (re int i=1;i<=n;++i)
        if (i==root[i]&&!killed[i]) ++ans;
    Ans[k+1]=ans;
    for (re int i=k;i>=0;--i) {
        int u=d[i];
        killed[u]=0,++ans;
        for (re int j=head[u];j;j=e[j].nxt) {
            int v=e[j].v; if (killed[v]) continue;
            if (check(u,v)) continue;
            else { merge(u,v); --ans; }
        }
        Ans[i]=ans;
    }
    for (re int i=1;i<=k+1;++i) printf("%d\n",Ans[i]);
    return 0;
}