Victor08 @ 2024-09-08 23:54:08
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[200005],q[200005],ans,f[200005],answ[200005];
vector<int> p[200005];
void build(){
for(int i=0;i<n;i++){
f[i]=i;
}
}
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void add(int x){
for(int i=0;i<p[x].size();i++){
if(!a[p[x][i]]){
if(find(x)!=find(p[x][i])){
ans--;
f[find(p[x][i])]=f[x];
}
}
}
}
int main(){
cin>>n>>m;
build();
while(m--){
int u,v;
cin>>u>>v;
p[u].push_back(v);
p[v].push_back(u);
}
cin>>k;
for(int i=k;i>=1;i--){
int x;
cin>>x;
a[x]=1;//被拿下
q[i]=x;//顺序
}
ans=n-k;
for(int i=0;i<n;i++){
if(!a[i]){
add(i);
}
}
answ[0]=ans;
for(int i=1;i<=k;i++){
ans++;
a[q[i]]=0;
add(q[i]);
answ[i]=ans;
}
for(int i=k;i>=0;i--){
cout<<answ[i]<<endl;
}
return 0;
}
by False0099 @ 2024-09-14 11:22:28
他题目里面给的是M的范围,然后N的范围最大可以是2M,所以你要初始化为两倍
by Victor08 @ 2024-09-19 23:49:59
确实,初始化为两倍就过了 谢谢!