目录
BZOJ1015 星球大战starwar题解ｃｏｄｅ
BZOJ1015 星球大战starwar
题目传送门
题解
比较经典的离线题目，我们将所有的数据读入之后，从后往前离线处理，用并查集维护就行了。注意一个星球被炸掉了之后，这个星球也会消失（即不算在联通块之内）。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=400005;
int n,m,q;
int ans;
int fa[maxn<<1],x[maxn],y[maxn],b[maxn],a[maxn],res[maxn];
std::vector<int>G[maxn];
/*==================Define Area================*/
int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int x,int y) {
x=find(x);y=find(y);
if(x==y) return ;
fa[x]=y;
ans--;
}
void init() {
for(int i=1;i<=n;i++) fa[i]=i;
}
int main() {
read(n);read(m);
ans=n;
init();
for(int i=1;i<=m;i++) {
read(x[i]);read(y[i]);
G[x[i]].push_back(y[i]);
G[y[i]].push_back(x[i]);
}
read(q);
for(int i=1;i<=q;i++) {
read(a[i]);
b[a[i]]=1;
}
for(int i=1;i<=m;i++) {
if(b[x[i]]||b[y[i]]) continue ;
unite(x[i],y[i]);
}
ans-=q;
for(int i=q;i>=1;i--) {
res[i]=ans++;
b[a[i]]=0;
for(int j=0;j<(int)G[a[i]].size();j++) {
if(b[a[i]]||b[G[a[i]][j]]) continue ;
unite(a[i],G[a[i]][j]);
}
}
printf("%d\n",ans);
for(int i=1;i<=q;i++) {
printf("%d\n",res[i]);
}
}
/*
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7
*/
转载于:https://www.cnblogs.com/Apocrypha/p/9433428.html
相关资源：JAVA上百实例源码以及开源项目
