Cod sursa(job #304048)

Utilizator mlazariLazari Mihai mlazari Data 10 aprilie 2009 19:40:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.09 kb
Program Dfs;
type PNod=^Nod;
     Nod=record
       x : longint;
       next : PNod;
     end;
var viz : array[1..100000] of boolean;
    v : array[1..100000] of PNod;
    n,m,cnt,i : longint;

procedure Adauga(var p : PNod; x : longint);
var q : PNod;
begin
  new(q);
  q^.x:=x;
  q^.next:=p;
  p:=q;
end;

procedure Citeste;
var Intrare : text;
    i,x,y : longint;
begin
  assign(Intrare,'dfs.in');
  reset(Intrare);
  readln(Intrare,n,m);
  for i:=1 to n do begin
    viz[i]:=false;
    v[i]:=nil;
  end;
  for i:=1 to m do begin
    readln(Intrare,x,y);
    Adauga(v[x],y);
    Adauga(v[y],x);
  end;
  close(Intrare);
end;

procedure DFS(x : longint);
var p : PNod;
begin
  viz[x]:=true;
  p:=v[x];
  while p<>nil do begin
    if not viz[p^.x] then DFS(p^.x);
    p:=p^.next;
  end;
end;

procedure Scrie;
var Iesire : text;
begin
  assign(Iesire,'dfs.out');
  rewrite(Iesire);
  write(Iesire,cnt);
  close(Iesire);
end;

begin
  Citeste;
  cnt:=0;
  for i:=1 to n do
   if not viz[i] then begin
     cnt:=cnt+1;
     DFS(i);
   end;
  Scrie;
end.