__Refine__ @ 2024-10-20 11:19:27
#include<bits/stdc++.h>
using namespace std;
struct bian
{
int nxt,to,cme;
}b[401010];
int dian[401001],tot;
long long n,m,k,atc[400001],ans[400001];
int fa[400001],all;
bool book[400001];
int fnd(int x)
{
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
inline void add(int x,int y)
{
b[++tot].nxt=dian[x];
b[tot].to=y;
dian[x]=tot;
b[tot].cme=x;
}
inline void solve(int x)
{
for(int i=dian[x];i;i=b[i].nxt)
{
int t=fnd(x);
int r=fnd(b[i].to);
if(t!=r&&book[b[i].to]==false)
{
fa[r]=t;
all--;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
cin>>k;
for(int i=1;i<=k;i++)
{
scanf("%d",&atc[i]);
book[atc[i]]=true;
}
all=n-k;
for(int i=1;i<=2*m;i++)
{
if(!book[b[i].cme]&&!book[b[i].to]&&fnd(b[i].cme)!=fnd(b[i].to))
{
all--;
fa[b[i].cme]=fa[b[i].to];
}
}
ans[k+1]=all;
for(int i=k;i>=1;i--)
{
book[atc[i]]=false;
all++;
solve(atc[i]);
ans[i]=all;
}
for(int i=1;i<=k+1;i++) cout<<ans[i]<<endl;
return 0;
}
```cpp
by cindyssx @ 2024-10-21 10:25:47
for(int i=1;i<=2*m;i++)
{
if(!book[b[i].cme]&&!book[b[i].to]&&fnd(b[i].cme)!=fnd(b[i].to))
{
all--;
fa[b[i].cme]=fa[b[i].to];
}
}
修改赋值语句
for(int i=1;i<=2*m;i++)
{
if(!book[b[i].cme]&&!book[b[i].to]&&fnd(b[i].cme)!=fnd(b[i].to))
{
all--;
fa[fnd(b[i].cme)]=fa[fnd(b[i].to)];
}
}