P1197 [JSOI2008]星球大战

    • 2.4K通过
    • 6.1K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 并查集 连通块 各省省选 2008 江苏 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。

    某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

    但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。

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

    输入输出格式

    输入格式:

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

    接下来的 $M$ 行,每行包括两个整数 $X$ , $Y$ ,其中( $0 < = X <> Y$ 表示星球 $x$ 和星球 $y$ 之间有 “以太” 隧道,可以直接通讯。

    接下来的一行为一个整数 $k$ ,表示将遭受攻击的星球的数目。

    接下来的 $k$ 行,每行有一个整数,按照顺序列出了帝国军的攻击目标。这 $k$ 个数互不相同,且都在 $0$ 到 $n-1$ 的范围内。

    输出格式:

    第一行是开始时星球的连通块个数。接下来的 $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
    1
    2
    3
    3

    说明

    [JSOI2008]

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。