楼下题解有误，献上我这个：

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
vector<int>G[N];
int fa[N],e[N],v[N],ans[N];
int findfa(int x){return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);}
int main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;cin>>x>>y;x++,y++;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int q;cin>>q;int k=q;
	for(int i=1;i<=n;i++)v[i]=1,fa[i]=i;
	for(int i=1;i<=q;i++)cin>>e[i],e[i]++,v[e[i]]=0;
	for(int i=1;i<=n;i++)if(v[i])e[++q]=i,v[i]=0;
	int sum=0;
	for(int i=q;i>=1;i--)
	{
		int x=e[i];
		v[x]=1;sum++;
		for(int y:G[x])if(v[y])
		{
			int ty=findfa(y);
			if(ty==x)continue;
			fa[ty]=x;
			sum--;
		}
		ans[i]=sum;
	}
	for(int i=1;i<=k+1;i++)cout<<ans[i]<<'\n';
	return 0;
}

[JSOI2008] 星球大战题解

题目描述

在遥远的银河系，存在N个星球（编号0到N-1）和M条双向航线。某天，K个星球依次被攻击并摧毁。每次攻击后，被摧毁的星球及其所有连接的航线将从图中移除。你的任务是计算每次攻击后剩余星球的连通分量数量。

输入输出格式

输入：

• 第一行：两个整数N（星球数）和M（航线数）。
• 接下来M行：每行两个整数u和v，表示一条航线连接星球u和v。
• 然后一行：一个整数K（攻击次数）。
• 接下来K行：每行一个整数x，表示第i次攻击摧毁的星球x。

输出：

• K个整数，每行一个，依次表示第1次攻击后到第K次攻击后的连通分量数量。

解题思路

1. 问题分析：直接删除节点并计算连通分量效率低，可采用逆向思维（从最后一次攻击开始，逐步恢复星球）。
2. 逆向处理：
   • 标记所有被摧毁的星球，初始状态为剩余星球（未被摧毁）。
   • 用并查集维护连通性，从最后一次攻击的星球开始，逐步恢复（添加）星球，合并其邻接航线，记录连通分量数量。
   • 倒序输出结果，得到每次攻击后的连通分量数。

代码实现

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

const int MAXN = 1e5 + 5;

int parent[MAXN];
int cnt; // 连通分量数量
bool removed[MAXN]; // 标记星球是否被摧毁
vector<int> adj[MAXN]; // 邻接表存储航线
int res[MAXN]; // 存储各阶段连通分量数

// 并查集查找根节点
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

// 合并两个连通分量
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[y] = x;
        cnt--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    // 读取航线，构建邻接表
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int K;
    cin >> K;
    vector<int> destroyed(K);
    for (int i = 0; i < K; ++i) {
        cin >> destroyed[i];
        removed[destroyed[i]] = true; // 标记初始被摧毁的星球
    }

    // 初始化：计算初始存活星球数量（未被摧毁）
    cnt = 0;
    for (int i = 0; i < N; ++i) {
        if (!removed[i]) {
            parent[i] = i; // 存活星球初始为独立连通分量
            cnt++;
        }
    }

    // 合并存活星球间的航线
    for (int i = 0; i < N; ++i) {
        if (!removed[i]) {
            for (int j : adj[i]) {
                if (!removed[j] && i < j) { // 避免重复合并
                    unite(i, j);
                }
            }
        }
    }

    res[K] = cnt; // 最后一次攻击后（所有被摧毁星球已移除）的连通分量数

    // 逆向恢复被摧毁的星球（从最后一次攻击开始）
    for (int i = K - 1; i >= 0; --i) {
        int x = destroyed[i];
        removed[x] = false; // 恢复星球x
        cnt++; // 添加新连通分量
        // 合并与x相邻的存活星球
        for (int y : adj[x]) {
            if (!removed[y]) { // y已存活
                unite(x, y);
            }
        }
        res[i] = cnt; // 记录恢复后的连通分量数
    }

    // 输出每次攻击后的结果
    for (int i = K - 1; i >= 0; --i) {
        cout << res[i] << '\n';
    }

    return 0;
}

C130 并查集 P1197 [JSOI2008] 星球大战