QHROAD - Phá đường

Tác giả: ladpro98

Ngôn ngữ: Pascal

{$MODE OBJFPC}
program QHROAD;
uses    math;
const   fi='';
        maxn=trunc(1e5)+9;
type    edge=record
                x,y:longint;
        end;
var     n,m,qq,i,j,x,y,scc:longint;
        e:array[1..maxn] of edge;
        q,res,lab:array[1..maxn] of longint;
        chk:array[1..maxn] of boolean;
        inp:text;

function root(u:longint):longint;
begin
        if lab[u]<=0 then exit(u);
        result:=root(lab[u]);
        lab[u]:=result;
end;

procedure union(u,v:longint);
begin
        if lab[u]<lab[v] then lab[v]:=u
        else begin
                if lab[u]=lab[v] then dec(lab[v]);
                lab[u]:=v;
        end;
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,n,m,qq);
        for i:=1 to m do readln(inp,e[i].x,e[i].y);
        for i:=1 to qq do readln(inp,q[i]);
        for i:=1 to qq do chk[q[i]]:=true;
        scc:=n;
        for i:=1 to m do if not chk[i] then begin
                x:=root(e[i].x);y:=root(e[i].y);
                if x<>y then begin
                        union(x,y);
                        dec(scc);
                end;
        end;
        for i:=qq downto 1 do begin
                res[i]:=scc;
                x:=root(e[q[i]].x);y:=root(e[q[i]].y);
                if x<>y then begin
                        union(x,y);
                        dec(scc);
                end;
        end;
        for i:=1 to qq do writeln(res[i]);
end.

Download