BZOJ 1015 星球大战
2024-08-27 16:08:32
Description
很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则这两个星球在同一个连通块中)。
Input
输入文件第一行包含两个整数,N (1 <= N <= 2M) 和M (1 <= M <= 200,000),分别表示星球的数目和以太隧道的数目。星球用0~N-1的整数编号。接下来的M行,每行包括两个整数X, Y,其中(0<=X<>Y
Output
输出文件的第一行是开始时星球的连通块个数。接下来的N行,每行一个整数,表示经过该次打击后现存星球的连通块个数。
Sample Input
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
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
Sample Output
1
1
1
2
3
3
1
1
2
3
3
HINT
Source
直观想法,时光倒流并查集。
code:
#include<cstdio>
#include<cstdlib>
using namespace std; #define maxn 400010
int father[maxn],side[maxn],next[maxn];
int toit[maxn],save[maxn],ans[maxn],cnt,tot,n,m;
bool exist[maxn],jud[maxn]; inline void init() { for (int i = ;i < n;++i) father[i] = i;} inline int find(int a) { if (father[a] != a) father[a] = find(father[a]); return father[a]; } inline void add(int a,int b) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; } inline void ins(int a,int b) { add(a,b); add(b,a); } int main()
{
freopen("1015.in","r",stdin);
freopen("1015.out","w",stdout);
scanf("%d %d",&n,&m); int i,j;
for (i = ;i <= m;++i)
{
int a,b; scanf("%d %d",&a,&b);
ins(a,b);
}
init(); int T; scanf("%d",&T);
for (i = ;i <= T;++i)
{
scanf("%d",save+i);
exist[save[i]] = true;
}
for (i = ;i < n;++i) if (!exist[i])
for (j = side[i];j;j = next[j])
if (!exist[toit[j]])
{
int r1 = find(i),r2 = find(toit[j]);
if (r1 != r2) father[r1] = r2;
}
for (i = ;i < n;++i) { if (!exist[i]&&!jud[find(i)]) ++tot,jud[find(i)] = true; }
ans[T+] = tot;
for (i = T;i;--i)
{
exist[save[i]] = false; ++tot;
for (j = side[save[i]];j;j = next[j])
if (!exist[toit[j]])
{
int r1 = find(save[i]),r2 = find(toit[j]);
if (r1 != r2) --tot;father[r1] = r2;
}
ans[i] = tot;
}
for (i = ;i <= T+;++i) printf("%d\n",ans[i]);
fclose(stdin); fclose(stdout);
return ;
}
最新文章
- 主席树——求静态区间第k大
- Bigendian 奇数内存地址取整形crash
- Safari 下用 ";location.href = filePath"; 实现下载功能的诡异 bug
- IFC
- Linux下安装配置Nexus
- 1070: [SCOI2007]修车 - BZOJ
- 函数lock_mode_stronger_or_eq 锁权限等级
- SQL Server 内存管理在64位时代的改变
- CentOS安装KVM步骤虚拟机,绝对实用!
- linux创建进程和等待进程退出
- JAVA实现的截屏程序
- git上传到github
- 关于PLC
- 【转】对GAMIT/GLOBK的基本认识
- jQuery(五)、筛选
- LeetCode第二十题-有效的括号
- bootstrap-treeview分级展示列表树的实现
- Java实现几种常见排序方法
- 自学Python1.8-python input/print用法 格式化输出
- hexo + Github Page 0元建立博客攻略
热门文章
- PHP本地环境搭配——WAMP不能启动, 一直处于红色图标或者橙色图标的解决办法
- C# 打开PPT文件另存为PPTX
- 08_android入门_android-async-http开源项目介绍及用法
- mybatis0205 一对多查询 复杂
- 使用systemtap调试linux内核
- 移动前端之 zepto
- Simple screenshot that explains the non-static invocation.
- Android Parcelable Trans byte[]
- Linux系统swap已分区但无法挂载与cryptswap1问题
- javascript社交平台分享-新浪微博、QQ微博、QQ好友、QQ空间、人人网