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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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来求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}