QHROAD - Phá đường
Tác giả: skyvn97
Ngôn ngữ: Pascal
program qhroad;
uses crt;
const
max=100100;
type
edge=record
u,v:longint;
isq:boolean;
end;
var
a:array[1..max] of edge;
up:array[1..max] of longint;
qr:array[1..max] of longint;
res:array[1..max] of longint;
m,n,q,cp:longint;
function find(x:integer):integer;
begin
if up[x]<0 then exit(x);
up[x]:=find(up[x]);
exit(up[x]);
end;
function join(a,b:integer):integer;
var
x,y:integer;
begin
x:=find(a);
y:=find(b);
if x=y then exit(0);
up[y]:=x;
exit(1);
end;
procedure loadgraph;
var
i:longint;
begin
read(n);
read(m);
read(q);
for i:=1 to n do up[i]:=-1;
for i:=1 to m do
begin
read(a[i].u);
read(a[i].v);
a[i].isq:=false;
end;
for i:=1 to q do
begin
read(qr[i]);
a[qr[i]].isq:=true;
end;
cp:=n;
end;
procedure process;
var
i:integer;
begin
for i:=1 to m do
if not a[i].isq then cp:=cp-join(a[i].u,a[i].v);
for i:=q downto 1 do
begin
res[i]:=cp;
cp:=cp-join(a[qr[i]].u,a[qr[i]].v);
end;
for i:=1 to q do writeln(res[i]);
end;
begin
// assign(input,'tmp.txt'); reset(input);
loadgraph;
process;
end.