Mr_think @ 2021-10-22 19:46:55
完整代码:
#include<cstdio>
using namespace std;
const int N=4e5+5;
int hd[N],to[N],nt[N],cnt;
inline void add(int x,int y){
to[++cnt]=y,nt[cnt]=hd[x],hd[x]=cnt;
}
struct node{
int x,y;
}b[N];
int fa[N],des[N];
bool vis[N];
int res,ans[N];
int find(int s){
if(fa[s]==s) return s;
return fa[s]=find(fa[s]);
}
void merge(int x,int y){fa[x]=y;}
int main(){
int n,m; scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) fa[i]=i;
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
b[i].x=x,b[i].y=y;
}
int k;scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d",&des[i]);
vis[des[i]]=1;
}
res=n-k;
// for(int x=0;x<n;x++){
// if(vis[x]) continue;
// for(int i=hd[x];i;i=nt[i]){
// int y=to[i];
// if(vis[y]) continue;
// x=find(x),y=find(y);
// if(x!=y) merge(x,y),res++;
// }
//
// }
for(int i=1;i<=m;i++){
int x=b[i].x,y=b[i].y;
if(vis[x]||vis[y]) continue;
x=find(x),y=find(y);
if(x!=y) merge(x,y),res--;
}
ans[k+1]=res;
for(int j=k;j>=1;j--){
int x=des[j];
vis[x]=0;
res++;
for(int i=hd[x];i;i=nt[i]){
int y=to[i];
if(vis[y]) continue;
x=find(x),y=find(y);
if(x!=y) merge(x,y),res--;
}
ans[j]=res;
}
for(int i=1;i<=k+1;i++) printf("%d\n",ans[i]);
return 0;
}
by Mr_think @ 2021-10-22 19:48:27
by L_cm_C5H6 @ 2022-03-14 20:44:25
@Mr_think 第一种x被find修改了枚举少了,外围改一个枚举变量就过了