【bzoj1015】[JSOI2008]星球大战starwar

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

给定一个无向图，求联通块个数，以及k次每次摧毁一个点后的联通块个数

将边和摧毁的点全记录下来，反着做即可

注意被摧毁的点不能算作联通块

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define MAXN 300010

int n,m;

int k;

int key[MAXN<<2],head[MAXN<<2],next[MAXN<<2];

int a[MAXN<<2],fa[MAXN<<2],ans[MAXN<<2];

int kk;

bool vis[MAXN<<2];

void link(int u,int v)

{

    key[kk]=v;

    next[kk]=head[u];

    head[u]=kk++;

}

int find(int x)

{

    return x==fa[x] ? x : fa[x]=find(fa[x]);

}

int main()

{

    memset(head,-1,sizeof(head));

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

    for (int i=1;i<=n;i++)

        fa[i]=i;

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

    {

        int x,y;

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

        link(x,y);

        link(y,x);

    }

    scanf("%d",&k);

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

        scanf("%d",&a[i]),vis[a[i]]=true;

    int z=n-k;

    for (int i=0;i<n;i++)

        if (!vis[i])

            for (int j=head[i];~j;j=next[j])

                if (!vis[key[j]])

                    if (find(i)!=find(key[j]))

                        fa[find(i)]=find(key[j]),z--;

    ans[k+1]=z;

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

    {

        vis[a[i]]=false;

        z++;

        for (int j=head[a[i]];~j;j=next[j])

            if (!vis[key[j]])

                if (find(a[i])!=find(key[j]))

                    fa[find(a[i])]=find(key[j]),z--;

        ans[i]=z;

    }

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

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

    return 0;

}