P1197 [JSOI2008] 星球大战 题解

题目链接

P1197 [JSOI2008] 星球大战

简要思路

看完题目的第一印象是——连通性。

图论中判断连通性很容易想到并查集，但是并查集只支持合并和查询，并不支持删除，怎么办呢？

考虑逆向思维，把删点的过程倒过来，看成加点和连边，那么此题就可以非常方便的用并查集来解决了。

和平就是好。

我们先把所有没被删除过的点建图，用并查集来维护。

之后倒着把每次删除的点加入，然后遍历它的所有连边，如果连边的终点没有被删除，那么我们就用并查集合并这两个点，并记录至答案数组中。

最后倒序输出答案数组即可。

完整代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=4e5+5;

int n,m,k;
int x[MAXN],y[MAXN],kkk[MAXN];//kkk[i] 表示第 i 个被删除的点
bool f[MAXN];//f[i] 代表点 i 是否被删除
int ans[MAXN],num;//num 连通块数量
int fa[MAXN];
std::vector<int> v[MAXN];

void add(int s,int e){v[s].push_back(e);v[e].push_back(s);}//加边
void init(){for(int i=0;i<n;i++)fa[i]=i;}//并查集初始化
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}//路径压缩
void merge(int x,int y){int fx=find(x),fy=find(y);if(fx!=fy){num--;fa[fy]=fx;}}//启发式合并[维护连通块数量]

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	
	std::cin>>n>>m;
	init();//并查集初始化[一定要在输入 n 之后，因为这个卡了 1.5h]
	for(int i=1;i<=m;i++){
		std::cin>>x[i]>>y[i];
		add(x[i],y[i]);//加边
	}

	std::cin>>k;
	for(int i=1;i<=k;i++)std::cin>>kkk[i],f[kkk[i]]=1;

	num=n-k;//一个点为一个连通块
	for(int i=1;i<=m;i++)//遍历所有边
		if(!f[x[i]]&&!f[y[i]])merge(x[i],y[i]);//保证点存在

	ans[k+1]=num;
	for(int i=k;i>=1;i--){
		int x=kkk[i];
		num++;//新增一个被删除的点
		f[x]=0;//被删除的点恢复
		for(int j=0;j<v[x].size();j++)
			if(!f[v[x][j]])merge(x,v[x][j]);//保证终点存在
		ans[i]=num;
	}
	
	for(int i=1;i<=k+1;i++)std::cout<<ans[i]<<endl;//倒序输出

	return 0;
}