Cod sursa(job #1606745)

Utilizator noi_totinoi toti noi_toti Data 20 februarie 2016 14:54:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.21 kb
program graf;
var f,g:text;
    t:array[0..1,1..400000] of longint;
    start:array[1..100000] of longint;
    viz:array[1..100000] of 0..1;
    m,n,x,y,k,nr,i:longint;
procedure df(nod:longint);
var p:longint;
    begin
         p:=start[nod];
         viz[nod]:=1;
         while p<>0 do
             begin
                  if viz[t[0,p]]=0 then
                    begin
                       df(t[0,p]);
                    end;
                  p:=t[1,p];
             end;
    end;

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



      close(f);
      close(g);
end.