Cod sursa(job #210831)

Utilizator RobybrasovRobert Hangu Robybrasov Data 29 septembrie 2008 18:22:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.16 kb
{
  Determinarea componentelor
  conexe prin parcurgerea in
  latime a grafului
}

type    adr=^noduri;
        noduri=record val:longint; urm:adr; end;
var     L:array[1..100000] of adr;
        E:array[1..100000] of boolean;
        C:array[1..100000] of longint;
        n,m,i,j,k,p,u,kont:longint;
        q:adr;
        f:text;

procedure bf(nod:longint);
begin
  p:=1; u:=1; C[1]:=nod;
  E[nod]:=true;
  while p<=u do
    begin
      q:=L[C[p]];
      while q<>nil do
        begin
          if not E[q^.val] then
            begin
              inc(u);
              C[u]:=q^.val;
              E[q^.val]:=true;
            end;
          q:=q^.urm;
          L[C[p]]:=L[C[p]]^.urm;
        end;
      inc(p);
    end;
end;

begin
  assign(f,'dfs.in');
  reset(f);
  readln(f,n,m);
  for k:=1 to m do
    begin
      readln(f,i,j);
      new(q);
      q^.val:=j; q^.urm:=L[i];
      L[i]:=q;
      new(q);
      q^.val:=i; q^.urm:=L[j];
      L[j]:=q;
    end;
  close(f);
  kont:=0;
  for i:=1 to n do
    if not E[i] then begin inc(kont); bf(i); end;
  assign(f,'dfs.out');
  rewrite(f);
  write(f,kont);
  close(f);
end.