coding_hong @ 2022-08-17 10:51:55
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
const int maxn=4e5+5;
using namespace std;
int n,m,k,t,ans,tp;
int fa[maxn],a[maxn],fin[maxn],stk[maxn];
bool vis[maxn],sam[maxn];
vector<int>g[maxn];
int find(int x) {
if(x==fa[x])
return x;
return fa[x]=find(fa[x]);
}
void unit(int x,int y) {
int xx=find(x),yy=find(y);
if(xx==yy)
return ;
fa[xx]=yy;
}
void cle() {
for(int i=1; i<=tp; i++)
sam[stk[i]]=0;
tp=0;
}
int main() {
//freopen("P1197myzao.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=0; i<=n-1; i++)
fa[i]=i;
for(int i=1,u,v; i<=m; i++) {
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
scanf("%d",&k);
for(int i=1,x; i<=k; i++) {
scanf("%d",&x);
vis[x]=1;
a[++t]=x;
}
for(int i=0; i<=n-1; i++) {
if(!vis[i]) {
for(int j=0; j<g[i].size(); j++) {
if(vis[g[i][j]])continue;
int ff=find(g[i][j]);
unit(i,g[i][j]);
if(sam[ff]==0) {
sam[ff]=1;
stk[++tp]=ff;
}
}
ans-=(tp-1);
cle();
}
}
//printf("ans: %d\n",ans);
for(int i=t; i>=1; i--) {
fin[i]=ans;
//printf("%d\n",ans);
vis[a[i]]=0;
for(int j=0; j<g[a[i]].size(); j++) {
if(vis[g[a[i]][j]])continue;
int ff=find(g[a[i]][j]);
if(sam[ff]==0) {
sam[ff]=1;
stk[++tp]=ff;
}
unit(a[i],g[a[i]][j]);
}
ans-=(tp-1);
cle();
}
printf("%d\n",ans);
for(int i=1; i<=t; i++)
printf("%d\n",fin[i]);
return 0;
}
```
by coding_hong @ 2022-08-18 16:33:47
已解决，此帖终
问题：
正确
int ff=find(g[i][j]);
//printf("%d %d %d",ff,i,g[i][j]);
if(sam[ff]==0&&find(i)!=ff) {
sam[ff]=1;
stk[++tp]=ff;
}
unit(i,g[i][j]);
}
错误
int ff=find(g[i][j]);
if(sam[ff]==0) {
sam[ff]=1;
stk[++tp]=ff;
}
unit(i,g[i][j]);
}