Cod sursa(job #670413)

Utilizator pongraczlajosLajos Pongracz pongraczlajos Data 28 ianuarie 2012 23:48:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.86 kb
type lista=^pont;
     pont=record
      cs:longint;
      kov:lista;
     end;

var x:array[1..100005] of lista;
    latott:array[1..100005] of boolean;
    n,m,i,a,b,k:longint;
    f:text;

procedure betesz(var s:lista; cs:longint);
var uj:lista;
begin
 new(uj);
 uj^.cs:=cs;
 uj^.kov:=s;
 s:=uj;
end;

procedure melysegi(cs:longint);
var p:lista;
begin
 latott[cs]:=true;
 p:=x[cs];
 while p<>nil do begin
  if (not latott[p^.cs]) then melysegi(p^.cs);
  p:=p^.kov;
 end;
end;

begin
assign(f,'dfs.in');
reset(f);
readln(f,n,m);
for i:=1 to m do begin
 readln(f,a,b);
 betesz(x[a],b);
 betesz(x[b],a);
end;
close(f);

k:=0;
for i:=1 to n do
 if (not latott[i]) then begin
                     inc(k);
                     melysegi(i);
                    end;

assign(f,'dfs.out');
rewrite(f);
write(f,k);
close(f);
end.