哪位大佬可以看一下哪里写挂了,或者提供一组hack数据,谢谢

P1197 [JSOI2008] 星球大战

SSL_wj @ 2021-01-22 20:48:20

#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,k,x,y,a[400010],nxt[400010],c[400010],d[400010],f[400010],head[400010],q[400010],s,tot=0;
bool ok[400010];
int find(int dep)
{
    if(f[dep]==dep)return dep;
    return f[dep]=find(f[dep]);
}
void add(int x,int y)
{
    a[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void merge(int x,int y)
{
    if(q[x]<q[y])f[x]=y;
    else if(q[x]>q[y])f[y]=x;
    else f[y]=x,q[x]++;
    --s;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)f[i]=i,q[i]=1;
    for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),add(++x,++y),add(y,x);
    scanf("%d",&k);
    for(int i=k;i>=1;i--)scanf("%d",&c[i]),ok[++c[i]]=1;
    s=n-k-1;
    for(int i=1;i<=n;i++)if(!ok[i])for(int j=head[i];j;j=nxt[j])if(!ok[a[j]]&&find(a[j])!=find(i))f[find(a[j])]=find(i);
    for(int i=0;i<=k;i++)
    {
        ok[c[i]]=0,s++;
        for(int j=head[c[i]];j;j=nxt[j])if(!ok[a[j]]&&find(a[j])!=find(c[i]))merge(find(a[j]),find(c[i]));
        d[i]=s;
    }
    for(int i=k;i>=0;i--)printf("%d\n",d[i]);
    return 0;
}

by SSL_wj @ 2021-01-23 09:26:18

全摧毁时建边未减连通块个数,此帖终


|