Cod sursa(job #257615)

Utilizator vladnVlad Nistorica vladn Data 13 februarie 2009 18:00:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.9 kb
type point=^nod;
     nod=record
     inf:longint;
     leg:point;
     end;
var  sel:array[1..100010] of boolean;
     a:array[1..100010] of point;
     n,m,i,x,y,nr:longint;
     f,g:text;
     p:point;
procedure bf(nod:longint);
begin
     sel[nod]:=true;
     while a[nod]<>nil do
     begin
          if sel[a[nod]^.inf]=false then
             bf(a[nod]^.inf);
          a[nod]:=a[nod]^.leg;
     end;
end;
begin
assign(f,'dfs.in');reset(f);
assign(g,'dfs.out');rewrite(g);
read(f,n,m);
for i:=1 to n do
    a[i]:=nil;
for i:=1 to m do
    begin
         read(f,x,y);
         if x<>y then begin
         new(p);p^.inf:=y;p^.leg:=a[x];a[x]:=p;
         new(p);p^.inf:=x;p^.leg:=a[y];a[y]:=p;
         end;
     end;
fillchar(sel,n,false);
nr:=0;
for i:=1 to n do
    if sel[i]=false then
    begin
       inc(nr);
       bf(i);
    end;
writeln(g,nr);
close(g);
end.