Cod sursa(job #274924)

Utilizator rendorzegAndrei Pavel rendorzeg Data 10 martie 2009 08:46:34
Problema Parcurgere DFS - componente conexe Scor 25
Compilator fpc Status done
Runda Arhiva educationala Marime 0.73 kb
var f,g:text;
    n,a,b,k,p,i,nc:integer;
    m:longint;
    d: array [1..1000,1..1000] of 0..1;
    v: array [1..1000] of 0..1;
    vb:boolean;
procedure dfs (k:byte);
var i:byte;
begin
v[k]:=1;
for i:=1 to n do if (v[i]=0) and (d[k,i]=1) then dfs(i);
end;
begin
assign(f,'dfs.in');
reset(f);
assign(g,'dfs.out');
rewrite(g);
read(f,n,m);
for i:=1 to m do begin
                 read(f,a,b);
                 d[a,b]:=1;
                 d[b,a]:=1;
                 end;

p:=1;
nc:=1;
repeat
vb:=true;
dfs(p);
for i:=1 to n do
if v[i]=0 then begin
               vb:=false;
               p:=i;
               inc(nc);
               break;
               end;
until vb;
write(g,nc);
close(f);
close(g);
end.