我不会做摧毁,于是反着做,就变成了合并连通块,倒序加边即可,时间复杂度 \(O((n+m)\alpha(n))\)。(大抵是吧
点击查看代码
#include<bits/stdc++.h>#define mem(aqwqawa,bqwqawa) memset((aqwqawa),(bqwqawa),sizeof(aqwqawa))
#define m0(aqwqawa) memset((aqwqawa),0,sizeof(aqwqawa))
#define lb(xqwqawa) ((xqwqawa)&-(xqwqawa))
#define lc(xqwqawa) ((xqwqawa)<<1)
#define rc(xqwqawa) (((xqwqawa)<<1)|1)
#define pb(Gqwqawa,xqwqawa) (Gqwqawa).push_back((xqwqawa))
#define For(Aqwqawa,Bqwqawa,Cqwqawa) for(int Aqwqawa=(Bqwqawa);Aqwqawa<=(Cqwqawa);Aqwqawa++)
#define Rep(Aqwqawa,Bqwqawa,Cqwqawa) for(int Aqwqawa=(Bqwqawa);Aqwqawa>=(Cqwqawa);Aqwqawa--)
#define in1(Aqwqawa) Aqwqawa=read()
#define in2(Aqwqawa,Bqwqawa) Aqwqawa=read(), Bqwqawa=read()
#define in3(Aqwqawa,Bqwqawa,Cqwqawa) Aqwqawa=read(), Bqwqawa=read(), Cqwqawa=read()
#define inn(Aqwqawa,Nqwqawa) For(Iqwqawa,1,Nqwqawa) Aqwqawa[Iqwqawa]=read();#define ll long long
using namespace std;
inline int read() {int xx= 0;int f= 1;char c = getchar();while(c<'0'||c>'9') { if(c=='-') f= -1;c= getchar();}while(c>='0'&&c<='9') {xx= (xx<<1)+(xx<<3)+(c^48);c= getchar();}return xx*f;
}
#define maxn 400050
int n,m,k;
vector<int>G[maxn];
bool vis[maxn];
int x[maxn];
int fa[maxn];
int find(int x) { return x==fa[x]?fa[x]:fa[x]=find(fa[x]); }
int ans[maxn];
signed main() {mem(vis,1);in2(n,m);For(i,1,m) {int u,v;in2(u,v);u++,v++;pb(G[u],v);pb(G[v],u);}in1(k);For(i,1,k) {in1(x[i]);x[i]++;vis[x[i]]=0;}int res=n-k;For(i,1,n) fa[i]=i;For(u,1,n) if(vis[u]) {for(auto v:G[u]) {if(vis[v]&&find(u)!=find(v)) {fa[find(u)]=find(v);res--;}}}ans[k+1]=res;Rep(i,k,1) {int u=x[i];vis[u]=1; res++;for(auto v:G[u]) if(vis[v]&&find(u)!=find(v)) {fa[find(u)]=find(v);res--;}ans[i]=res;}For(i,1,k+1) cout<<ans[i]<<'\n';
}