Cod sursa(job #146308)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 1 martie 2008 15:36:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.02 kb
type pelem=^elem;
     elem=record
       info:longint;
       next:pelem;
     end;
var fi,fo:text;
    n,m,i,j,v1,v2,ct:longint;
    list:array[1..100000]of pelem;
    s:array[1..100000]of byte;
procedure push(var first:pelem; vl:longint);
var p:pelem;
begin
  new(p);
  p^.info:=vl;
  p^.next:=first;
  first:=p;
end;
procedure pop(var first:pelem; var vl:longint);
var p:pelem;
begin
  vl:=first^.info;
  p:=first;
  first:=first^.next;
  dispose(p);
end;
procedure df(nod:longint);
var aux:longint;
begin
  s[nod]:=1;
  while list[nod]<>nil do
    begin
      pop(list[nod],aux);
      if s[aux]=0 then df(aux);
    end;
end;
begin
  assign(fi,'dfs.in'); reset(fi);
  assign(fo,'dfs.out'); rewrite(fo);
  read(fi,n,m);
  for i:=1 to m do
    begin
      read(fi,v1,v2);
      push(list[v1],v2);
      push(list[v2],v1);
    end;
  ct:=0;
  for i:=1 to n do
    if s[i]=0 then
      begin
        inc(ct);
        df(i);
      end;
  writeln(fo,ct);
  close(fi);
  close(fo);
end.