Cod sursa(job #164739)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 24 martie 2008 19:18:14
Problema Parcurgere DFS - componente conexe Scor 50
Compilator fpc Status done
Runda Arhiva educationala Marime 0.78 kb
program dfs;
var A : array [1..100000,1..1000] of longint;
    ok : array [1..100000] of boolean;
    nr : array [1..100000] of longint;
    f,g : text;
    i,j,m,n,l,S : longint;

procedure ds(i:integer);
var k : longint;
begin
ok[i] := false;
if nr[i]>0 then
           for k := 1 to nr[i] do
           if ok[A[i,k]] then ds(A[i,k]);
end;


begin
assign(f,'dfs.in');reset(f);
assign(g,'dfs.out');rewrite(g);

readln(f,n,m);

for i := 1 to n do begin
ok[i] := true;
nr[i] := 0;
end;

for l := 1 to m do begin
readln(f,i,j);
nr[i] := nr[i]+1;
A[i,nr[i]] := j;
nr[j] := nr[j]+1;
A[j,nr[j]] := i;
end;

S := 0;
for i := 1 to n do
if ok[i] then begin
              ds(i);
              inc(S);
              end;

write(g,S);
close(f);
close(g);
end.