yangjunhan1 @ 2024-09-17 20:21:04
30pts
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,k,ks[N],f[N],ans[N],ns,fs;
bool vis[N],sv[N],t=1;
vector<int> d[N];
int fsb(int x){
return f[x]==x?x:f[x]=fsb(f[x]);
}
void merge(int x,int y){
if(vis[y]) return ;
x=fsb(x),y=fsb(y);
if(x!=y) ns--;
f[x]=y;
}
int main(){
cin>>n>>m;
while(m--){
int x,y;
cin>>x>>y;
x++;
y++;
d[x].push_back(y);
d[y].push_back(x);
sv[x]=sv[y]=1;
}
cin>>k;
for(int i=1;i<=k;i++){
cin>>ks[i];
ks[i]++;
vis[ks[i]]=1;
}
for(int i=1;i<=n;i++)
if(!vis[i]){
f[i]=i;
ns++;
}
ans[k+1]=ns;
for(int i=k;i;i--){
int nk=ks[i];
vis[nk]=0;
if(!sv[nk]){
if(t) ns++;
ans[i]=ns;
t=0;
continue;
}
f[nk]=nk;
ns++;
for(int j=0;j<d[nk].size();j++)
merge(nk,d[nk][j]);
ans[i]=ns;
}
for(int i=1;i<=k+1;i++) cout<<ans[i]<<endl;
return 0;
}
40pts
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,k,ks[N],f[N],ans[N],ns,fs;
bool vis[N],sv[N];
vector<int> d[N];
int fsb(int x){
return f[x]==x?x:f[x]=fsb(f[x]);
}
void merge(int x,int y){
if(vis[y]) return ;
x=fsb(x),y=fsb(y);
if(x!=y) ns--;
f[x]=y;
}
int main(){
cin>>n>>m;
while(m--){
int x,y;
cin>>x>>y;
x++;
y++;
d[x].push_back(y);
d[y].push_back(x);
sv[x]=sv[y]=1;
}
cin>>k;
for(int i=1;i<=k;i++){
cin>>ks[i];
ks[i]++;
vis[ks[i]]=1;
}
for(int i=1;i<=n;i++)
if(!vis[i]){
f[i]=i;
ns++;
}
ans[k+1]=ns;
for(int i=k;i;i--){
int nk=ks[i];
if(!sv[nk]){
ans[i]=++ns;
continue;
}
vis[nk]=0;
f[nk]=nk;
ns++;
for(int j=0;j<d[nk].size();j++)
merge(nk,d[nk][j]);
ans[i]=ns;
}
for(int i=1;i<=k+1;i++) cout<<ans[i]<<endl;
return 0;
}
by yangjunhan1 @ 2024-09-17 20:33:43
已A,结贴。