Cod sursa(job #210815)

Utilizator RobybrasovRobert Hangu Robybrasov Data 29 septembrie 2008 17:34:15
Problema Parcurgere DFS - componente conexe Scor 95
Compilator fpc Status done
Runda Arhiva educationala Marime 1.01 kb
type    adr=^noduri;
        noduri=record val:longint; urm:adr; end;
var     L:array[1..100001] of adr;
        E:array[1..100001] of boolean;
        C:array[1..100001] of longint;
        n,m,i,j,k,p,u,kont:longint;
        q:adr;
        f:text;

procedure bf(nod:longint);
var q:adr;
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
          inc(u);
          C[u]:=q^.val;
          E[q^.val]:=true;
          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.