题解 | #[JSOI2008]星球大战STARWAR#

并查集 + 邻接表 + 逆向思维

逆向思维:

原题意：共要删除 k 个点，问：每次删除过后，连通块个数是多少？
逆向思维：删点 ==> 加点、连边   对！没错，变成了加点与连边

所以最开始，我们只对 n-k 个点进行合并操作就行，然后枚举每个要删除的点（注意是从后向前枚举）
对于每个枚举到的 "要删点"，我们执行 加点 与 连边操作(合并操作)
加点：加上该点
连边：对 该点 和 与其直接相连的点们 进行并查集的合并操作

ps：被删点 和 被删点 可能直接相连，比如 题目让我们先删 6，再删 3，但 3、6 直接相连
当我们枚举时，因为是逆着枚举，所以我们会先枚举到 3 再枚举到 6

当枚举到 3 时：3 和 6 直接相连，但此时我们不应对他们进行合并操作
因为这个时候图上还没有点6，6 还没有被我们加上去呢！！6 会在接下来也就是枚举到它时才被加上去！

当我们枚举到 6 时：3 和 6 直接相连，此时我们可以对他们进行合并操作了，因为 3、6 此时都已在图上啦

邻接表

一条"链子"叫 单链表，很多条"链子"就组成了邻接表，我们使用邻接表来存储与每个被删点直接相连的点
为什么用邻接表？？？当然是因为开二维数组开不下啊！！！

~~没学过邻接表的，可以学一下，图论题离不开邻接表~~

代码中 一些变量或语句 的解释

D[i]：指第 i 个被删的点
st[i]：i 这个点是第几个被删除
ans[i]：第 i 个点被删除后，目前的连通块块数

x、y 都是被删点的时候为什么要判断 st[x]、st[y] 谁大？
这个 就是我们在 逆向思维Part 所提到的了，x、y 都是被删点 且 两者直接相连的时候
为了避免 枚举到一个点的时候，另一个点还没有被加到图上，我们需要考虑 它们两个被删的先后顺序

语句:res减1 执行时的场合 ==> 合并两个不相连的连通块时

Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e6+10;

PII p[N];
int h[N],e[N],ne[N],idx;  // 邻接表
int st[N],fa[N],D[N],ans[N];
int n,m,k;

void add(int a,int b){  // 添加 a 指向 b 的边
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
} 

void Init(){
     memset(h,-1,sizeof h);   // 邻接表初始化
     for(int i=0;i<n;i++) fa[i]=i;  // 并查集初始化，点是0~n-1（注意题目）
}

void Input(){
    cin>>n>>m;
    for(int i=0;i<m;i++)  cin>>p[i].first>>p[i].second;
    cin>>k;
    for(int i=1;i<=k;i++)  cin>>D[i],st[D[i]]=i;
}

void solve(){
    int res=n-k; //逆向思维，删除k个点后，剩n-k个
    for(int i=0;i<m;i++){
        int x=p[i].first,y=p[i].second;
        if(!st[x]&&!st[y]){   // 对剩余的n-k个点先进行合并操作
            x=find(x),y=find(y);
            if(x!=y) fa[x]=y,res--; 
        }
        else if(!st[x]&&st[y])  add(y,x);   // 说明y是被删点，通过邻接表存储和y相连的点
        else if(st[x]&&!st[y])  add(x,y);  // 说明x是被删点，...
        else { // 说明x、y都是被删点，...
            if(st[x]>st[y]) add(y,x);  
            else add(x,y);
        }
    } 

    for(int i=k;i>=1;i--){
        ans[i]=res;
        int id=D[i];
        res++;   //记得先加上1：加点操作
        for(int ii=h[id];ii!=-1;ii=ne[ii]){  //合并与D[i]直接相连的点
            int j=e[ii];
            id=find(id),j=find(j);
            if(id!=j){
                res--;
                fa[id]=j;
            }
        }
    }
    cout<<res<<endl;
    for(int i=1;i<=k;i++) cout<<ans[i]<<endl;
}

int main(){
    Input();   Init();   solve();
    return 0;
}