洛谷 P1197 [JSOI2008] 星球大战 做题记录
我不会做摧毁，于是反着做，就变成了合并连通块，倒序加边即可，时间复杂度 \(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';
}