• [1508] 火烧赤壁2

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 上次出了一道火烧赤壁的题目给当时的新生,也就是你们的上一届学长们做,那么这次,我又想到了另一个想法。
    上次的火烧赤壁的题号为1274
    这次稍微难一点,我们来个火烧赤壁2吧。

    Hungar个人很喜欢曹操这个人,所以这次有机会穿越到三国时代,他想帮助曹操打赢赤壁之战。
    但是他去晚了,当他穿越到那的时候发现大火已经在蔓延了,所以他能做的就是马上告诉曹操把已经着火的船的锁链(船与船相连都是靠锁链达到的)给破坏掉使火不会蔓延到附近的船只。

    现在告诉你曹操一共有N艘船,M条铁链,船只编号从0开始到n-1。
    然后再告诉你依次着火的船只编号,问舍弃那艘船以后,剩下的船只能形成几个连通块(只要是被铁链连在一起的全部船只,就算一共连通块)。
    船与船之间可能存在多条锁链。

  • 输入
  • 输入包括第一行两个整数,N(1 <= N <= 2M)和M(1 <= M <= 200,000)。
    接下来M行,每行包括两个整数x和y(x != y),分别表示编号为x和y的船只被一根锁链连起来。
    再接下来一个正整数T表示着火船只的数量。
    接下来T行,每行包含一个整数z表示被烧船只的编号,编号不会出现一样的,也就是说已经被烧的船只不会再去烧它。
  • 输出
  • 输出z+1个数,第一行为着火前这些船的连通块数,后z行表示每次依次烧掉一只船后,剩下的连通块数。
  • 样例输入
  • 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
    
  • 提示
  • 并查集
  • 来源
  • Hungar
  • 操作

显示春菜