Cod sursa(job #563645)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 25 martie 2011 17:02:35
Problema Parcurgere DFS - componente conexe Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 0.64 kb
var     a:array[1..100000] of longint;
        b:array[1..100000] of boolean;
        n,m,x,y,i,j,nr,k:longint;
        f,g:text;

begin
  assign(f,'dfs.in');
  reset(f);
  assign(g,'dfs.out');
  rewrite(g);
  readln(f,n,m);

  for i:=1 to m do
    begin
      readln(f,x,y);
      if (a[x]=0)and(a[y]=0) then a[y]:=x else
      if a[x]=0 then a[x]:=a[y] else a[y]:=a[x];
    end;
  nr:=0;

  for i:=1 to n do
    begin
      j:=i;
      while a[j]>0 do begin k:=a[j]; a[j]:=-1; j:=k; end;
      if a[j]=0 then
        begin
          inc(nr);
          a[j]:=-1;
        end;
    end;
  writeln(g,nr);
  close(g);
end.