求助大佬，60分调了1h了，1，8，9，10RE

百年流光 @ 2021-02-27 16:10:16

#include<bits/stdc++.h>
using namespace std;
const int N=800001;
struct v
{
    vector<int> to;
}a[N];
int b[N][2],c[N],s[N],flag[N],fa[N],x,y,num,sl=0;
int find(int x1)
{
    if (fa[x1]==x1) return x1;
    else return fa[x1]=find(fa[x1]);
}
void merge()
{
    if (find(x)!=find(y))
    {
        num--;
        fa[find(y)]=x;
    }
}
int main()
{
    int n,m,k,i,j;
    cin>>n>>m;
    for (i=0;i<=n;++i)
    {
        fa[i]=i;
        flag[i]=0;
    }
    for (i=1;i<=m;++i)
    {
        cin>>x>>y;
        b[i][1]=x;
        b[i][2]=y;
    }
    cin>>k;
    num=n-k;
    for (i=1;i<=k;++i)
    {
        cin>>x;
        c[i]=x;
        flag[x]=1;
    }
    for (i=1;i<=m;++i)
    {
        x=b[i][1],y=b[i][2];
        if (flag[x]==0&&flag[y]==0)
          merge();
        else
        {
            a[x].to.push_back(y);
            a[y].to.push_back(x);
        }
    }
    for (i=k;i>=1;--i)
    {
        int u=c[i];
        sl++;
        s[sl]=num;
        flag[u]=0;
        num++;
        for (j=0;j<=a[u].to.size()-1;++j)
        {
            x=u;
            y=a[u].to[j];
            if (flag[y]==0)
              merge();
        }
    }
    sl++;
    s[sl]=num;
    for (i=sl;i>=1;--i)
      cout<<s[i]<<endl;
    return 0;
}

by 青莲梵音 @ 2021-02-27 16:50:21

我的代码是满分，你看看

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N=400000+5;
int n,m,k,head[N],num=0,father[N],flag[N],tim[N],tot[N];
struct edge
{int u,v,next;}ed[N*2];
void build(int u,int v)
{
    ed[++num].u=u;
    ed[num].v=v;
    ed[num].next=head[u];
    head[u]=num;
}
int getfather(int x)
{
    if (x==father[x]) return x;
    return father[x]=getfather(father[x]);
}
int main()
{
    memset(flag,0,sizeof(flag));
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        build(u,v);
        build(v,u);
    }
    scanf("%d",&k);
    for (int i=1;i<=k;i++)
    {
        int x;
        scanf("%d",&x);
        flag[x]=1;tim[i]=x;
    }
    for (int i=0;i<=n;i++)
    father[i]=i;
    int blk=n-k,top=0;
    for (int i=1;i<=num;i++)
    {
        int u=ed[i].u,v=ed[i].v;
        if (flag[u]==0&&flag[v]==0&&getfather(u)!=getfather(v))
        {
            blk--;
            father[getfather(u)]=getfather(v);
        }
    }
    tot[++top]=blk;
    for (int i=k;i>=1;i--)
    {
        int u=tim[i];
        blk++;flag[u]=0;
        for (int j=head[u];j!=-1;j=ed[j].next)
        {
            int v=ed[j].v;
            if (flag[v]==0&&getfather(u)!=getfather(v))
            {
                blk--;
                father[getfather(u)]=getfather(v);
            }
        }
        tot[++top]=blk;
    }
    for (int i=top;i>=1;i--)
    printf("%d\n",tot[i]);
    return 0;
}

by 百年流光 @ 2021-02-27 18:27:33

**几乎一样**QAQ

by Rushroom @ 2021-07-07 18:50:28

vector用的空间太大，爆了