stdKonjac's Blog

An AC a day keeps the WA away ~

【星球大战】

题目背景

JSOI2008试题。(不排除改过题目背景的可能性)

题目描述

很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。

现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则这两个星球在同一个连通块中)。

输入格式

输入文件第一行包含两个整数,N(1<=N<=2M)和 M(1≤M≤200,000),分别表示星球的数目和以太隧道的数目。星球用 0~N-1的整数编号。

接下来的 M 行,每行包括两个整数 X,Y,其中 X,Y∈[0,N) 且 X≠Y ,表示星球 X 和星球 Y 之间有以太隧道。注意所有的以太隧道都是双向的。

之后输入一个整数 K(K≤N),表示帝国计划打击的星球个数。

接下来 K 行,每行一个星球编号 Di(0≤Di<N),表示打击的星球编号顺序。

输出格式

第一行是开始时星球的连通块个数。
接下来的 K 行,每行一个整数,表示经过该次打击后现存星球的连通块个数。

样例数据 1

输入

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

输出

1
1
1
2
3
3

备注

【数据范围】
对于 20% 的数据,M≤10;
对于另 20% 的数据,N≤10000;
对于 100% 的数据,M≤200000;

正着建图然后删边实现起来非常复杂……但是倒着来添边就很简单了,先把不被攻击的星球连接起来,然后倒序添加要被打击的星球,之后求并查集若不在一个块中,说明原先在一个块中,就blcok-1。话说为啥为TLE两个点还是不知道……

下面是TLE两点的代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.