# P1197 [JSOI2008] 星球大战
# 题意
n 个星球，m 条边，k 此摧毁，每次都会摧毁一个星球，摧毁一次求一次联通块，没摧毁时也要输出一次
# 解法
求联通块有两种方法
- 利用 dfs 或者 bfs 从每一个点出发，把能到达的点都标记，每一个点都走一次，时间复杂度为 O (n)，
- 使用并查集，单独 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; | |
} |
