Cod sursa(job #846678)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 2 ianuarie 2013 16:57:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.95 kb
program dfs;
  type lista=^celula;
       celula=record
                info:longint;
                next:lista;
              end;
  var f1,f2:text;
      n,m,i,x,y,k:longint;
      a:array [1..100000] of lista;
      viz:array [1..100000] of byte;
      buf:array[1..100000] of byte;
      r:lista;
procedure dfs(x:longint);
  var q:lista;
  begin
    viz[x]:=1;
    q:=a[x];
    while q<>nil do
      begin
        if viz[q^.info]=0 then dfs(q^.info);
        q:=q^.next;
      end;
  end;
begin
  assign(f1,'dfs.in');
  reset(f1);
  settextbuf(f1,buf);
  assign(f2,'dfs.out');
  rewrite(f2);
  readln(f1,n,m);
  for i:=1 to m do
    begin
      readln(f1,x,y);
      new(r);
      r^.info:=y;
      r^.next:=a[x];
      a[x]:=r;
      new(r);
      r^.info:=x;
      r^.next:=a[y];
      a[y]:=r;
    end;
  for i:=1 to n do
    if viz[i]=0 then begin inc(k); dfs(i); end;
  writeln(f2,k);
  close(f1);close(f2);
end.