Cod sursa(job #157062)

Utilizator gabyromaRomanescu Gabriela gabyroma Data 12 martie 2008 20:50:45
Problema Parcurgere DFS - componente conexe Scor 60
Compilator fpc Status done
Runda Arhiva educationala Marime 0.94 kb
program df_pe_liste;
type point=^nod;
     nod=record
     inf:integer;
     leg:point;
     end;

var prim:array[1..100000] of point;
    f,g:text;
    n,m,nr:longint;
    sel:array[1..100000] of boolean;

procedure citire;
var i,x,y:integer; p:point;
begin
readln(f,n,m);
for i:=1 to n do prim[i]:=nil;
for i:=1 to m do begin
  readln(f,x,y);
  new(p);
  p^.inf:=x;
  p^.leg:=prim[y];
  prim[y]:=p;
  new(p);
  p^.inf:=y;
  p^.leg:=prim[x];
  prim[x]:=p;
  end;
end;

procedure df(x:integer);
var p:point;
begin
sel[x]:=true;
p:=prim[x];
while p<>nil do begin
  if not sel[p^.inf] then df(p^.inf);
  p:=p^.leg;
  end;
end;

procedure conex;
var i:integer;
begin
nr:=0;
for i:=1 to n do
  if not sel[i] then begin
    df(i);
    inc(nr);
    end;
end;


begin
assign(f,'dfs.in');
assign(g,'dfs.out');
reset(f);
rewrite(g);
citire;
fillchar(sel,n,false);
conex;
writeln(g,nr);
close(f);
close(g);
end.