Cod sursa(job #402675)

Utilizator mimarcelMoldovan Marcel mimarcel Data 24 februarie 2010 08:08:50
Problema Parcurgere DFS - componente conexe Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.14 kb
const maxn=100000;
type matrice=array[1..maxn,0..maxn]of longint;
     vector=array[1..maxn+1]of boolean;
     coada=array[1..maxn]of longint;
var a:matrice;
    n,m,i,x,y:longint;
    viz:vector;
    pi,ps,r,rez:longint;
    c:coada;

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);
                 inc(a[x][0]);
                 a[x][a[x][0]]:=y;
                 inc(a[y][0]);
                 a[y][a[y][0]]:=x;
                 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];
  for i:=1 to a[x][0] do begin
                         y:=a[x][i];
                         if viz[y]=false then begin
                                              inc(pi);
                                              c[pi]:=y;
                                              viz[y]:=true;
                                              end;
                         end;
  inc(ps);
  end;
while viz[r] do inc(r);
until r>n;
writeln(rez);
close(output);
close(input);
end.