[JSOI2008] 星球大战

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400000;
const int MAXM = 200000;
int n, m; // 点数（编号从 0 ~ n-1）、边数
// 基础存图，e[u] 存所有 u 连接到的点
vector<int> e[MAXN + 5];
int k;               // 被摧毁的星球数量
int star[MAXN + 5];  // 按顺序存被摧毁的星球
bool flag[MAXN + 5]; // 标记每个星球是否被摧毁了
int nowAns;          // 记录当前的连通块数量（不包括被摧毁的星球）
int ans[MAXN + 5];   // 记录每个星球被摧毁后的答案（有几个连通块）
// 并查集
int fa[MAXN + 5];
int findFa(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> star[i];
        flag[star[i]] = true;
    }
    // 并查集初始化
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    // 建立除了被摧毁的星球之外的连接关系
    nowAns = n - k;
    for (int u = 0; u <= n - 1; u++)
    {
        if (flag[u] == true)
            continue;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (flag[v] == true)
                continue;
            // 合并 u,v
            int rootU = findFa(u);
            int rootV = findFa(v);
            if (rootU != rootV)
            {
                fa[rootU] = rootV;
                nowAns--;
            }
        }
    }
    ans[k] = nowAns; // k 个星球都被摧毁之后的状态
    // 从后往前恢复每个星球
    for (int i = k; i >= 1; i--)
    {
        // 恢复 star[i]
        int u = star[i];
        nowAns++;
        flag[u] = false; // 这个点现在没有被摧毁
        // 恢复所有 u 的连接关系
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (flag[v] == true)
                continue;
            // 恢复 u,v（合并 u,v）
            int rootU = findFa(u);
            int rootV = findFa(v);
            if (rootU != rootV)
            {
                fa[rootU] = rootV;
                nowAns--;
            }
        }
        // 记录答案，恢复了第 i~k 个点之后，就是前 i-1 个点被摧毁时的状态
        ans[i - 1] = nowAns;
    }
    for (int i = 0; i <= k; i++)
        cout << ans[i] << "\n";
    return 0;
}