# P1197 [JSOI2008] 星球大战

image-20210226153906812

# 题意

n 个星球,m 条边,k 此摧毁,每次都会摧毁一个星球,摧毁一次求一次联通块,没摧毁时也要输出一次

# 解法

求联通块有两种方法

  1. 利用 dfs 或者 bfs 从每一个点出发,把能到达的点都标记,每一个点都走一次,时间复杂度为 O (n),
  2. 使用并查集,单独 n 个点联通块就是 n 个,当两个点连接起来并且这两个点分别属于两个不同的联通块时,把他们合并成一个集合,联通块数量 - 1,时间复杂度差不多等于边的数量,>O (m)

如果只是求一次联通块的数量显然第一种方法更优,但是这道题每少一个点就要求一次联通块,如果用第一种方法时复 O (kn),这道题会超时,这时如果用并查集正着来做,时复 O (mk),也会超时,但是换一种思路,这道题要摧毁星球,我们倒着来,修建星球,每修建一个求一次联通块,而这时并查集时复就是常数级别 O (max (m,k)),每修建一个多了一个点,联通块 + 1,看看和这个点相连的点是否属于一个集合,属于就 - 1,一个 pair 存点,再用链式前向星存一下图

# CODE

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const double pi=acos(-1);
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const int eps=1e-4;
struct node{
	int to,next;
}e[MAXN];
int fa[MAXN],ans[MAXN],head[MAXN],dead[MAXN];
bool vis[MAXN];
pair<int,int> b[MAXN];
int tot,n,m,k;
void add(int u,int v){
	e[tot]={v,head[u]};
	head[u]=tot++;
}
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
} 
void remerge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy) fa[fx]=fy;
}
int main(){
	ios;
	cin>>n>>m;
	for(int i=0;i<=n;i++) fa[i]=i;
	memset(head,-1,sizeof head);
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		b[i]={u,v};
		add(u,v);
		add(v,u);
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>dead[i];
		vis[dead[i]]=1;  // 标记这个点被摧毁了
	}
	int num=n-k;
	for(int i=1;i<=m;i++){
        // 如果条边连接的两个点都没有被摧毁且两者不在同一个集合
		if(!vis[b[i].first] && !vis[b[i].second] && find(b[i].first)!=find(b[i].second)){
			remerge(b[i].first,b[i].second);
			num--;
		}
	}
    // 此时就是所有星球被摧毁的联通块
	ans[0]=num;
	for(int i=k;i>=1;i--){
		num++; // 加一个点联通块 + 1
		vis[dead[i]]=0;  // 清除这个点的标记
		for(int j=head[dead[i]];~j;j=e[j].next){  // 遍历这个点相连的点
			int v=e[j].to;
			if(!vis[v] && find(v)!=find(dead[i])){  // 相连点存活且不在一个集合联通块 - 1
				num--;
				remerge(v,dead[i]);
			}
		}
		ans[k-i+1]=num;
	}
    // 倒着输出
	for(int i=k;i>=0;i--) cout<<ans[i]<<'\n';
	return 0;
}

利用 dfs 求:

20 分,其中一个地方爆栈了,可以换成 bfs 来求

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=400010;
const double pi=acos(-1);
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const int eps=1e-4;
struct node{
	int to,next;
}e[200010];
int n,m,tot,k,x,y,js;
int head[MAXN];
bool vis[MAXN],used[MAXN],book[MAXN];
void add(int u,int v){
	e[tot]={v,head[u]};
	head[u]=tot++;
}
void dfs(int x){
	vis[x]=1;
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].to;
		if(vis[v] || used[v]) continue;
		dfs(v);
	}
}
int main(){
	ios;
	memset(head,-1,sizeof head);
	cin>>n>>m;
	while(m--){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	cin>>k;
	for(int i=0;i<=n-1;i++){
		if(vis[i] || used[i]) continue;
		js++;
		dfs(i);
	}
	cout<<js<<'\n';
	while(k--){
		memset(vis,0,sizeof vis);
		js=0;
		cin>>x;
		used[x]=1;
		for(int i=0;i<=n-1;i++){
			if(vis[i] || used[i]) continue;
			js++;
			dfs(i);
		}
		cout<<js<<'\n';
	}
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝