第九个样例过不了,WA了好久了,QwQ,大佬麻烦看一看
#include<bits/stdc++.h>
using namespace std;
long long n,m,fa[200010],x[200010],y[200010],k,h[200010],ans,ra[200010];
bool kil[200010],vis[200010];
long long find_father(long long num)
{
if(fa[num]==num)
{
return num;
}
return fa[num]=find_father(fa[num]);
}
vector <long long> line[200010],point[200010];
int main()
{
scanf("%lld%lld",&n,&m);
for(long long i=0;i<n;i++)
{
fa[i]=i;
}
for(long long i=1;i<=m;i++)
{
scanf("%lld%lld",&x[i],&y[i]);
line[x[i]].push_back(i);
line[y[i]].push_back(i);
point[x[i]].push_back(y[i]);
point[y[i]].push_back(x[i]);
}
scanf("%lld",&k);
for(long long i=1;i<=k;i++)
{
scanf("%lld",&h[i]);
kil[h[i]]=true;
}
ans=n-k;
for(long long i=0;i<n;i++)
{
if(kil[i]==false)
{
for(long long j=0;j<line[i].size();j++)
{
if(vis[line[i][j]]==false)
{
if(kil[point[i][j]]==false)
{
long long xf=find_father(i),yf=find_father(point[i][j]);
vis[line[i][j]]=true;
if(xf!=yf)
{
ans--;
fa[xf]=yf;
}
}
}
}
}
}
ra[k]=ans;
for(long long i=k;i>=1;i--)
{
kil[h[i]]=false;
long long lg=0;
for(long long j=0;j<line[h[i]].size();j++)
{
if(vis[line[h[i]][j]]==false)
{
if(kil[point[h[i]][j]]==false)
{
long long xf=find_father(h[i]),yf=find_father(point[h[i]][j]);
vis[line[h[i]][j]]=true;
if(xf!=yf)
{
lg++;
fa[xf]=yf;
}
}
}
}
ans-=lg-1;
ra[i-1]=ans;
}
for(long long i=0;i<=k;i++)
{
printf("%lld\n",ra[i]);
}
}
这是记录:
https://www.luogu.com.cn/record/173676189
orz orz