cqbzhr @ 2024-05-02 22:14:04
#include <bits/stdc++.h>
using namespace std;
int n,m,k,x,y,fa[400005],a[400005],vis[400005],tot,op,s[400005];
struct node{
int x,y,h,pr;
}fa2[400005];
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void unite(int x,int y){
int u=find(x),v=find(y);
if(u!=v)fa[u]=v;
}
int add(int x,int y){
op++;
fa2[op].x=x;
fa2[op].y=y;
fa2[op].pr=fa2[x].h;
fa2[x].h=op;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++){
fa[i]=i;
fa2[i].h=-1;
}
for(int i=1;i<=m;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
cin>>k;
for(int i=1;i<=k;i++){
cin>>a[i];
vis[a[i]]=1;
}
for(int i=1;i<=op;i++){
if(!vis[fa2[i].x]&&!vis[fa2[i].y])unite(fa2[i].x,fa2[i].y);
}
for(int i=0;i<n;i++){
if(!vis[i]&&fa[i]==i)tot++;
}
s[k+1]=tot;
for(int i=k;i>=1;i--){
int nx=a[i];
tot++;
vis[nx]=0;
for(int j=fa2[nx].h;j!=-1;j=fa2[j].pr){
int ny=fa2[j].y;
if(!vis[ny]&&fa[find(nx)]!=fa[find(ny)]){
unite(nx,ny);
tot--;
}
}
s[i]=tot;
}
for(int i=1;i<=k+1;i++){
cout<<s[i]<<"\n";
}
return 0;
}by cqbzhr @ 2024-05-02 22:15:40
求大佬帮忙，又MLE又TLE的
by 123huchenghao @ 2024-06-28 14:28:06
#include<cstdio>
int n,m,t,sum,cnt,tot;
int st[400010],fa[400010],head[400010],lian[400010],ans[400010];
bool flag[400010];
struct edg{
int to,next,from;
}edge[400010];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].from=x;
edge[cnt].next=head[x];
head[x]=cnt;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
scanf("%d",&t);
for(register int i=1;i<=t;i++) {
scanf("%d",&st[i]);
flag[st[i]]=true;
}
for(register int i=0;i<n;i++) fa[i]=i;
int tot=n-t;
for(int i=1;i<=cnt;i++){
int u=find(edge[i].to),v=find(edge[i].from);
if(u!=v&&!flag[edge[i].to]&&!flag[edge[i].from]) tot--,fa[u]=v;
}
ans[t+1]=tot;
for(int i=t;i;i--){
int x=st[i];
tot++,flag[x]=false;
for(int j=head[x];j;j=edge[j].next){
int u=find(x),v=find(edge[j].to);
if(!flag[edge[j].to]&&u!=v) tot--,fa[v]=u;
}
ans[i]=tot;
}
for(int i=1;i<=t+1;i++) printf("%d\n",ans[i]);
return 0;
}