Cod sursa(job #1606737)

Utilizator noi_totinoi toti noi_toti Data 20 februarie 2016 14:50:08
Problema Parcurgere DFS - componente conexe Scor 50
Compilator fpc Status done
Runda Arhiva educationala Marime 0.75 kb
Program graf;
Var n,m,i,k:longint;
 a:array[1..10000,1..10000] of 0..1;
 viz:array[1..100000] of 0..1;
 f,g:text;

Procedure citire;
Var i,j,k:integer;
Begin
 assign(f,'dfs.in'); reset(f);
 assign(g,'dfs.out'); rewrite(g);
 readln(f,n,m);
 For k:=1 to m do
  begin
   read(f,i,j);
   a[i,j]:=1;
   a[j,i]:=1;
  end;
 close(f);
end;

Procedure df(start:integer);
Var i:integer;
Begin
 viz[start]:=1;
 For i:=1 to n do
  If (a[start,i]=1) and (viz[i]=0) then
                                    df(i);
end;


BEGIN
 citire;

 df(1);
 k:=1;

 For i:=2 to n do
  begin
   If viz[i]<>1 then
                 begin
                  k:=k+1;
                  df(i);
                 end;
  end;

 write(g,k);

 close(g);
END.