[数据结构与算法]P1197 [JSOI2008]星球大战 题解

题目传送门

题意简述

给定一张无向图，每次删去一个节点，问每次操作后的连通块个数。

分析

$m\le 2\times 10^5,n\le 2?m$，如果每次暴力删点再 bfs，必定超时。

还记得上次提到的 [USACO16OPEN]Closing the Farm 吗？这两题非常非常相似，我们可以将删点转换为加点，倒序处理，再求连通块即可。

算法步骤如下：

1. 建图，读入每次删去的节点。
2. 先预处理出起始图（即把幸免遇难的节点做并查集），统计连通块数。
3. 倒序处理，先是连通块数 $cnt\leftarrow cnt+1$（自成一块），再维护即可。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int maxm=2e6+10;
const int maxn=maxm<<1;
int n,m;
int k;
int fa[maxn];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x!=y)fa[x]=y;
}

struct edge{
	int to,nxt;
}e[maxm<<1];
int head[maxn],idx;
void link(int x,int y){
	e[++idx]={y,head[x]};
	head[x]=idx;
}
int del[maxn];
bool damage[maxn];
int ans[maxn];
int main(){
	cin>>n>>m;
	for(int i=0;i<=n;i++)fa[i]=i;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;link(x,y);link(y,x);
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>del[i];
		damage[del[i]]=true;
	}
	for(int i=1;i<=n;i++){
		if(!damage[i]){
			for(int j=head[i];j;j=e[j].nxt){
				int v=e[j].to;
				if(!damage[v]){
					merge(i,v);
				}
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(fa[i]==i&&!damage[i]){
			cnt++;
		}
	}int fin=cnt;
	for(int i=k;i>=1;i--){
		int x=del[i];
		damage[x]=false;
		cnt++;
		for(int j=head[x];j;j=e[j].nxt){
			int v=e[j].to;
			if(!damage[v]){
				if(find(x)!=find(v)){
					fa[find(x)]=find(v);
					cnt--;
				}
			}
		}
		ans[i]=cnt;
	}
	for(int i=1;i<=k;i++){
		cout<<ans[i]<<'\n';
	}
	cout<<fin;
	return 0;
}

小结

这是本人写的第 $4$ 篇并查集题解了。

并查集真的很多变，做了这么多变式并查集题目，相信大家可以好好掌握，秒切并查集。