Cod sursa(job #1086985)

Utilizator alexcruceruAlexandru Cruceru alexcruceru Data 18 ianuarie 2014 19:36:35
Problema Parcurgere DFS - componente conexe Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 0.87 kb
program nrdecomponenteconexe;
type sir=array[1..100000]of longword;
var f,g:text;
    a,b,co:sir;
    n,m,i,j,k,x,y,aux:longword;


begin
assign(f,'grader_test1.in');reset(f);
assign(g,'dfs.out');rewrite(g);
readln(f,n,m);
k:=0;
for i:=1 to n do co[i]:=0;
for i:=1 to m do
  begin
  readln(f,x,y);
  a[i]:=x;
  b[i]:=y;
  end;
for i:=m downto 1 do
  for j:=1 to i-1 do
    if a[j]>a[j+1] then
      begin
      aux:=a[j];
      a[j]:=a[j+1];
      a[j+1]:=aux;
      aux:=b[j];
      b[j]:=b[j+1];
      b[j+1]:=aux;
      end;

for i:=1 to m do
  begin
  if (co[a[i]]=0)and(co[b[i]]=0) then begin inc(k); co[a[i]]:=k; co[b[i]]:=k; end
    else if co[a[i]]=0 then co[a[i]]:=co[b[i]]
      else if co[b[i]]=0 then co[b[i]]:=co[a[i]];
  end;

for i:=1 to n do
  if co[i]=0 then inc(k);

write(g,k);
close(f);
close(g);
end.