Cod sursa(job #402676)

Utilizator mimarcelMoldovan Marcel mimarcel Data 24 februarie 2010 08:08:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.32 kb
const maxn=100000;
type plista=^lista;
     lista=record
           nod:longint;
           urm:plista;
           end;
     liste=array[1..maxn]of plista;
     vector=array[1..maxn+1]of boolean;
     coada=array[1..maxn]of longint;
var a:liste;
    n,m,i,x,y:longint;
    viz:vector;
    pi,ps,r,rez:longint;
    c:coada;
    p:plista;

begin
assign(input,'dfs.in');
reset(input);
assign(output,'dfs.out');
rewrite(output);
readln(n,m);
for i:=1 to m do begin
                 readln(x,y);
                 new(p);
                 p^.nod:=y;
                 p^.urm:=a[x];
                 a[x]:=p;
                 new(p);
                 p^.nod:=x;
                 p^.urm:=a[y];
                 a[y]:=p;
                 end;

r:=1;
rez:=0;
repeat
pi:=1;
ps:=1;
c[1]:=r;
viz[r]:=true;
inc(rez);
while ps<=pi do
  begin
  x:=c[ps];
  p:=a[x];
  while p<>nil do begin
                  y:=p^.nod;
                  if viz[y]=false then begin
                                       inc(pi);
                                       c[pi]:=y;
                                       viz[y]:=true;
                                       end;
                  p:=p^.urm;
                  end;
  inc(ps);
  end;
while viz[r] do inc(r);
until r>n;
writeln(rez);
close(output);
close(input);
end.