题解 Luogu P1197 [JSOI2008]星球大战

Luogu P1197 [JSOI2008]星球大战

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

本题看起来是将每次所轰炸的点所连的边断掉，但实际操作极其复杂。

实际上我们可以把所有操作倒过来，从摧毁星球到建造星球

统计初态（原题末态，星球已摧毁完毕，即现在还未开始建造星球）

每次建造一个星球，相当于多一个集合，再已经存在的星球且与其有连边的星球合并为一个集合,若合并成功则少一个集合，每执行一个星球后统计一遍答案，最后倒序输出即可

Code:

#include<bits/stdc++.h>
#define M 220000
using namespace std;

int n,m;
int last[M<<1];
int beat[M<<1];
int c,k;
int f[M<<1],v[M<<1];
vector<int> li[M<<1];
int ans[M];
inline int find(int x){
    if(f[x]==-1) return x;
    return f[x]=find(f[x]);
}
inline int merge(int x,int y){
    int t1=find(x),t2=find(y);
    if(t1==t2) return 0;
    f[t1]=t2;
    return 1;
}
int main (){
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i)
        f[i]=-1;
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        li[x].push_back(y);
        li[y].push_back(x);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;++i){
        scanf("%d",&beat[i]);
        v[beat[i]]=1;
    }
    for(int i=0;i<n;++i){
        if(!v[i]){
            int S=li[i].size();
            for(int j=0;j<S;++j){
                if(!v[li[i][j]]){
                    merge(i,li[i][j]);
                }
            }
        }
    }

    for(int i=0;i<n;++i){
        if(f[i]==-1)
            if(!v[i])
                c++;
    }
    int fina=c;
    for(int i=k;i>=1;--i){
        c++;
        for(int j=li[beat[i]].size()-1;j>=0;--j){
            v[beat[i]]=0;
            if(!v[li[beat[i]][j]])
            c-=merge(beat[i],li[beat[i]][j]);   
        }
        ans[i]=c;
    }
    for(int i=1;i<=k;++i){
        printf("%d\n",ans[i]);
    }
    printf("%d\n",fina);
}