Cod sursa(job #379174)

Utilizator cristinabCristina Brinza cristinab Data 30 decembrie 2009 21:39:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.02 kb
{componente conexe cu DF}

type ref=^nod;
     nod=record
         vf:longint;
         leg:ref;
         end;
     domeniu=0..1;

var sel:array[1..100000] of domeniu;
    prim:array[1..100000] of ref;
    n,m,nr:longint;

procedure adaug(x,y:longint);
var c:ref;
begin
new(c);
c^.vf:=y;
c^.leg:=prim[x];
prim[x]:=c;
end;

procedure citire;
var i,x,y:longint;
begin
assign(input,'dfs.in'); reset(input);
readln(n,m);
for i:=1 to m do
    begin
    readln(x,y);
    adaug(x,y);
    adaug(y,x);
    end;
close(input);
end;

procedure df(i:longint);
var p:ref;
begin
sel[i]:=1;
p:=prim[i];

while p<>nil do
      begin
      if sel[p^.vf]=0 then df(p^.vf);
      p:=p^.leg;
      end;
end;

procedure rezolvare;
var i:longint;
begin

nr:=0;

for i:=1 to n do
    if sel[i]=0 then
       begin
       df(i);
       inc(nr);
       end;
end;

begin
assign(output,'dfs.out'); rewrite(output);
citire;
rezolvare;
if nr=0 then writeln(1)
        else writeln(nr);
close(output);
end.