Cod sursa(job #1606744)

Utilizator noi_totinoi toti noi_toti Data 20 februarie 2016 14:53:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.23 kb
program mire;
var n,m,nr,i:longint;
    f,g:text;
    a:array[0..1,0..400000] of longint;
    co,start:array[1..100001] of longint;
    viz:array[1..100001] of 0..1;
    bufin,bufout:array[1..1 shl 16] of byte;
procedure citire;
var i,x,y,k:longint;
begin
  assign(f,'dfs.in'); reset(f);
  assign(g,'dfs.out'); rewrite(g);
  settextbuf(f,bufin); settextbuf(g,bufout);
   readln(f,n,m);
   k:=0;
   for i:=1 to m do
     begin
       readln(f,x,y);
       inc(k);
       a[0,k]:=y;
       a[1,k]:=start[x];
       start[x]:=k;
       inc(k);
       a[0,k]:=x;
       a[1,k]:=start[y];
       start[y]:=k;
     end;
  close(f);
end;
procedure bf(nod:longint);
var st,sf,p:longint;
begin
  st:=1; sf:=1; co[st]:=nod; viz[nod]:=1;
  while st<=sf do
    begin
      p:=start[co[st]];
      while p<>0 do
        begin
            if viz[a[0,p]]=0 then
               begin
                 inc(sf);
                 co[sf]:=a[0,p];
                 viz[a[0,p]]:=1;
               end;
            p:=a[1,p];
        end;
       inc(st);
    end;
end;
begin
  citire; nr:=0;
  for i:=1 to n do
     if viz[i]=0 then
       begin
         inc(nr);
         bf(i);
       end;
  writeln(g,nr);
  close(g);
end.