P1197 [JSOI2008]星球大战——链式前向星+并查集

https://www.luogu.org/problem/P1197

这道题算是关闭农场的加强版吧，数据有点大，矩阵存不下；

也是记录删点操作，从后往前加边；

先将每个点都算成一个连通块，然后每连一条边连通块数就减一；

加一个点时不要忘记连通块数+1，然后合并；

还有数组要开大；

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int pre[maxn*],last[maxn],other[maxn*],from[maxn*],l;

int n,m,k;

int out_block[maxn*],delete_order[maxn*];

int num_block[maxn*],tot_block;

int father[maxn*];

void add(int x,int y)

{

    l++;

    from[l]=x;

    pre[l]=last[x];

    last[x]=l;

    other[l]=y;

}

int getfather(int x)

{

    if(father[x]==x) return x;

    father[x]=getfather(father[x]);

    return father[x];

}

void merge(int x,int y)

{

    int fx=getfather(x);

    int fy=getfather(y);

    father[fx]=fy;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    scanf("%d",&k);

    for(int i=;i<=k;i++)

    {

        scanf("%d",&delete_order[i]);

        out_block[delete_order[i]]=;

    }

    tot_block=n-k;

    for(int i=;i<=n;i++) father[i]=i;

    for(int i=;i<=m*;i++)

    {

        if(!out_block[from[i]]&&!out_block[other[i]]&&getfather(from[i])!=getfather(other[i]))

        {

            merge(from[i],other[i]);

            tot_block--;

        }

    }

    num_block[k+]=tot_block;

    for(int i=k;i>=;i--)

    {

        out_block[delete_order[i]]=;

        tot_block++;

        for(int p=last[delete_order[i]];p;p=pre[p])

        {

            int v=other[p];

            if(!out_block[v]&&getfather(delete_order[i])!=getfather(v))

            {

                tot_block--;

                merge(delete_order[i],v);

            }

        }

        num_block[i]=tot_block;

    }

    for(int i=;i<=k+;i++)

    {

        printf("%d\n",num_block[i]);

    }

    return ;

}