Cod sursa(job #1340608)

Utilizator mirelabocsabocsa mirela mirelabocsa Data 11 februarie 2015 22:11:25
Problema Parcurgere DFS - componente conexe Scor 45
Compilator fpc Status done
Runda Arhiva educationala Marime 1.11 kb
program mire;
var t:array[0..1,0..200000] of integer;
  start,co,viz:array[1..100000] of longint;
  n,m,b,j:longint;
  f,g:text;
procedure citire;
var i,j,k,x,y:longint;
begin
assign(f,'dfs.in'); reset(f);
  readln(f,n,m);
  k:=0;
   for i:=1 to m do
     begin
        inc(k);
        readln(f,x,y);
        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;
    close(f);
end;
procedure bf(nod,c: longint);
var st,sf,i,p:longint;
begin
  st:=1;
  sf:=1;
  co[st]:=nod;
  viz[nod]:=c;
  while st<=sf do
    begin
      p:=start[co[st]];
      while p<>0 do
        begin
          if viz[t[0,p]]<>c then
            begin
              inc(sf);
              co[sf]:=t[0,p];
              viz[t[0,p]]:=c;
            end;
            p:=t[1,p];
        end;
        st:=st+1;
    end;
end;
begin
 citire;
 b:=0;
  for j:=1 to n do
   if viz[j]=0 then
     begin
      inc(b);
      bf(j,b);
     end;
   assign(g,'dfs.out'); rewrite(g);
   writeln(g,b);
  close(g);

end.