Cod sursa(job #386443)

Utilizator arnold23Arnold Tempfli arnold23 Data 24 ianuarie 2010 20:24:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.85 kb
type lista=^elem;
     elem=record
       csp:longint;
       kov:lista;
     end;

var f:text;
    v:array[1..100000] of lista;
    lat:array[1..100000] of boolean;
    n,m,a,b,d,i:longint;

procedure betesz(w,e:longint);
var p:lista;
begin
 new(p);
 p^.csp:=e;
 p^.kov:=v[w];
 v[w]:=p;
end;

procedure dfs(s:longint);
var q:lista;
begin
 lat[s]:=true;
 q:=v[s];
 while q<>nil do
  begin
    if not lat[q^.csp] then dfs(q^.csp);
    q:=q^.kov;
  end;
end;

begin
 assign(f,'dfs.in');
 reset(f);
 readln(f,n,m);
 for i:=1 to m do begin
   readln(f,a,b);
   betesz(a,b);
   betesz(b,a);
 end;
 close(f);

 d:=0;
 for i:=1 to n do
  if not lat[i] then begin
                        dfs(i);
                        inc(d);
                     end;

 assign(f,'dfs.out');
 rewrite(f);
 writeln(f,d);
 close(f);

end.