学步园

星球大战
StarWar/.IN/.OUT/.PAS/.EXE
问题描述
很久以前，在一个遥远的银河……对反抗军来说，这是一个黑暗的时刻。虽然帝国军的
终极武器“死亡星球”已经被摧毁，帝国的军队仍然把反抗军从隐藏的军事基地中赶出，并
在整个银河系展开追逐。1
考虑到邪恶的帝国完全有能力在短时间内制造出“死亡星球”的替代品，为了避免被一
次全部歼灭，反抗军的指挥官决定把部队分散在很多星球上。可是，这样会带来通讯上的问
题。某些星球之间可以通过“以太”隧道直接通讯，而没有隧道相连的星球之间的通讯就需
要其他星球帮忙转发。因此，只有两个星球之间存在一条由“以太”隧道拼接成的路径，它

们才可以正常通讯。

银河历2008 年4 月1 日凌晨，反抗军最担心的事情还是发生了。反抗军司令部收到
间谍的秘密通知：帝国军成功制造出第二代“死亡星球”，并将依次摧毁如下星球（星球列
表略）。指挥官希望迅速计算出每次攻击之后通讯网络的连通情况，即反叛军所占据的星球
被分成了多少个连通支，从而帮助决定在何时发动反击。
输入
输入文件starwar.in 的第一行包含两个整数N (2 ≤ N ≤ 2M)和M (1 ≤ M ≤
200,000)，分别表示星球的数目和“以太”隧道的数目。星球用0 到N – 1 的整数编号。
接下来的M 行，每行包含两个整数X 和Y (0 ≤ X ≠ Y < N)，表示星球X 和星球Y
之间有“以太”隧道，可以直接通讯。

接下来的一行包含一个整数K，表示将遭受攻击的星球的数目。
接下来的K 行，每行一个整数，按照顺序列出了帝国军的攻击目标。这K 个数互不相
同，且都在0 到N – 1 的范围内。
输出
请将输出写至文件starwar.out。
输出文件应该包含K + 1 行，每行一个整数。

第一个整数表示开始时通讯网络的连通支个数。
接下来的第I (1 ≤ I ≤ K)个整数，表示在攻击列表上的第I 个星球被摧毁后，通讯网
络的连通支个数。

使用并查集倒着处理

{$inline on}
program starwar;
var
  tot,now,n,m,i,j,k,x,y:longint;
  yes:array [0..400001] of boolean;
  ans,dl,point,next,father,root:array [0..400001] of longint;

procedure connect (u,v:longint);inline;
begin
  inc(tot);
  point[tot]:=v;
  next[tot]:=root[u];
  root[u]:=tot;
end;

function find (now:longint):longint;inline;
begin
  if father[now]=0 then exit(now);
  father[now]:=find(father[now]);
  exit(father[now]);
end;

begin
  assign(input,'starwar.in');
  reset(input);
  assign(output,'starwar.out');
  rewrite(output);
  read(n,m);
  for i:=1 to m do
    begin
      read(x,y);
      inc(x);
      inc(y);
      connect(x,y);
      connect(y,x);
    end;
  fillchar(yes,sizeof(yes),true);
  read(k);
  for i:=1 to k do
    begin
      read(dl[i]);
      inc(dl[i]);
      yes[dl[i]]:=false;
    end;
  now:=n-k;
  for i:=1 to n do
    if (yes[i]) then
      begin
        x:=find(i);
        j:=root[i];
        while j<>0 do
          begin
            if yes[point[j]] then
              begin
                y:=find(point[j]);
                if y<>x then
                  begin
                    father[y]:=x;
                    dec(now);
                  end;
              end;
            j:=next[j];
          end;
      end;
  ans[k+1]:=now;
  for i:=k downto 1 do
    begin
      inc(now);
      j:=root[dl[i]];
      while j<>0 do
        begin
          if yes[point[j]] then
            begin
              y:=find(point[j]);
              if y<>dl[i] then
                begin
                  father[y]:=dl[i];
                  dec(now);
                end;
            end;
          j:=next[j];
        end;
      yes[dl[i]]:=true;
      ans[i]:=now;
    end;
  for i:=1 to k+1 do
    writeln(ans[i]);
  close(input);
  close(output);
end.