【BZOJ】1015: [JSOI2008]星球大战starwar

1015: [JSOI2008]星球大战starwar

题意:一个点数为N(1<= 40w),边数为M(1<=20w)的图，总共删除k个节点，问开始以及每次删除一个节点之后图的连通块数?

思路:逆序并查集 即每次往图中加点；主要是因为逆序时，并查集的关系不会改变，最终在同一个连通块中的节点，之前一定还是在一个并查集中；

需注意加点时，如果该点还是孤立节点，这时就需要++sum;当然如果开始就增加连通分块的个数，之后加点的时候减去那也是一样的；

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N = ;

const int M = ;

int f[N],vis[N],del[N],ans[N];

int tot,head[N],sum;

void init()

{

    tot = ;memset(head,,sizeof(head));

}

struct Edge{

    int to,Next;

}e[M<<];

inline void ins(int u,int v)

{

    e[++tot].Next = head[u]; e[tot].to = v; head[u] = tot;

}

int Find(int a)//**

{

    return a == f[a]?f[a]:f[a] = Find(f[a]);

}

void dfs(int u)

{

    vis[u] = ;

    for(int id = head[u];id;id = e[id].Next){

        int v = e[id].to;

        if(vis[v]) continue;

        f[v] = Find(f[u]);

        dfs(v);

    }

}

int add(int u)

{

    for(int id = head[u];id;id = e[id].Next){

        int v = e[id].to;

        if(vis[v] == ) continue;

        int fv = Find(v);

        if(f[u] == u){f[u] = fv;continue;}

        if(f[u] != u && f[u] != fv) sum--;

        f[fv] = f[u];

    }

    if(f[u] == u) sum++;//孤立节点

}

int main()

{

    int n,m,k,u,v;

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

    init();

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

        scanf("%d%d",&u,&v);

        ins(u,v);ins(v,u);

    }

    scanf("%d",&k);

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

        scanf("%d",del + i);

        vis[del[i]] = ;//2表示删除的节点，1表示在图中的节点

    }

    sum = ;

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

    for(int i = ;i < n;i++)if(!vis[i]) dfs(i),sum++;

    ans[k] = sum;

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

        add(del[i]),vis[del[i]] = , ans[i] = sum;

    }

    for(int i = ;i <= k;i++) printf("%d\n",ans[i]);

}