Cod sursa(job #673860)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 4 februarie 2012 23:49:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.79 kb
program dfs;
var f,g:text;
    a:array of array of longint;
    n,m,i,j,nr,x,y:longint;
    viz:array[0..100000] of 0..1;

procedure df (i:longint);
var j:longint;
begin
   for j:=1 to a[i,0] do
    if viz[a[i,j]]=0 then
    begin
     viz[a[i,j]]:=1;
     df(a[i,j]);
    end;
end;

begin
 assign (f,'dfs.in'); reset (f);
 assign (g,'dfs.out'); rewrite (g);
 readln (f,n,m);
 setlength (a,n+1);
 for i:=1 to n do
  setlength (a[i],1);
 for i:=1 to m do
 begin
  readln (f,x,y);
  a[x,0]:=a[x,0]+1;
  setlength (a[x],length(a[x])+1);
  a[x,a[x,0]]:=y;
  a[y,0]:=a[y,0]+1;
  setlength (a[y],length (a[y])+1);
  a[y,a[y,0]]:=x;
 end;
 for i:=1 to n do
  if viz[i]=0 then
  begin
   viz[i]:=1;
   nr:=nr+1;
   df(i);
  end;
  write (g,nr);
  close (f);
  close (g);
end.