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.

Download