加了并查集和读入优化,但还是T了四个点,求大佬帮忙看一眼QWQ
代码如下:
#include<bits/stdc++.h>
using namespace std;
int fa[400100],head[400100],z[400100],ans,bui[400100];
bool vis[400100];
int find(int a)
{
int b=a,c;
while(a!=fa[a])
a=fa[a];
while(b!=a)
{
c=b;
b=fa[b];
fa[c]=a;
}
}
struct o
{
int to,next,from;
}a[400100];
int ii;
void add(int x,int y)
{
a[++ii].to=y;
a[ii].from=x;
a[ii].next=head[x];
head[x]=ii;
}
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
int main()
{
int n,m;
n=read(),m=read();
for(int i=1;i<=n;i++)
{
fa[i]=i;
head[i]=-1;
}
for(int i=1;i<=m;i++)
{
int x,y;
x=read(),y=read();
add(x,y);
add(y,x);
}
int kk;
kk=read();
ans=n-kk;
for(int i=1;i<=kk;i++)
{
int k;
k=read();
vis[k]=1;
z[i]=k;
}
for(int i=1;i<=2*m;i++)
{
if(vis[a[i].from]==0&&vis[a[i].to]==0)
{
int oo=find(a[i].from),pp=find(a[i].to);
if(oo!=pp)
{
fa[pp]=oo;
ans--;
}
}
}
bui[kk+1]=ans;
for(int i=kk;i>=1;i--)
{
int o=z[i];
vis[o]=0;
ans++;
for(int j=head[o];j!=-1;j=a[j].next)
{
int oo=find(a[j].to),pp=find(o);
int df=fa[oo],gh=fa[pp];
if(vis[a[j].to]==0&&df!=gh)
{
ans--;
fa[oo]=fa[pp];
}
}
bui[i]=ans;
}
for(int i=1;i<=kk+1;i++)
cout<<bui[i]<<endl;
return 0;
}