Cod sursa(job #701327)

Utilizator aliveLechintan Adrian alive Data 1 martie 2012 15:14:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.87 kb
// parcurgere DFS
type muchie=^nod;
     nod=record
         n:longint;
         a:muchie;
         end;

var
 f,g:text;
 n,m,i,j,x,y,k,kk:longint;
 v:array[1..100000] of muchie;
 chk:array[1..100000] of boolean;
 a:array[1..100000] of longint;
 p:muchie;


procedure dfs(qx:longint);
var
qp:muchie;
begin
 chk[qx]:=true;
 qp:=v[qx];

 while qp<>nil do
  begin
  if chk[qp^.n]=false then dfs(qp^.n);
  qp:=qp^.a;
  end;
end;

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

 for i:=1 to m do
  begin
  read(f,x,y);
  new(p);  p^.n:=y;  p^.a:=v[x];  v[x]:=p;
  new(p);  p^.n:=x;  p^.a:=v[y];  v[y]:=p;
  end;

 kk:=0;
 for k:=1 to n do
  if chk[k]=false then begin
                       inc(kk);
                       dfs(k);
                       end;

writeln(g,kk);
 close(f); close(g);
end.