Cod sursa(job #274990)

Utilizator rendorzegAndrei Pavel rendorzeg Data 10 martie 2009 09:58:03
Problema Parcurgere DFS - componente conexe Scor 5
Compilator fpc Status done
Runda Arhiva educationala Marime 1.63 kb
type lista=^elem;
     elem=record
              v:longint;
              urm:lista;
          end;
var g:array [1..100000] of lista;
    viz:array [1..100000] of 0..1;
    f,h:text;
    m,n,i,x,y,l,nc:longint;
    q,w:lista;
    vb:boolean;
procedure dfs(k:longint);
var p:lista;
begin
viz[k]:=1;
p:=g[k];
while p<>Nil do begin
                if (viz[p^.v]=0) then dfs(p^.v);
                p:=p^.urm;
                end;
end;
begin
assign(f,'dfs.in');
reset(f);
assign(h,'dfs.out');
rewrite(h);
read(f,n,m);
for i:=1 to m do begin
                 read(f,x,y);
                 new(q);
                 q^.v:=y;
                 if g[x]=nil then begin
                                  g[x]:=q;
                                  q^.urm:=nil;
                                  end
                             else begin
                                  q^.urm:=g[x];
                                  g[x]:=q;
                                  end;
                 new(w);
                 w^.v:=x;
                 if g[y]=nil then begin
                                  g[y]:=w;
                                  w^.urm:=nil;
                                  end
                             else begin
                                  w^.urm:=g[y];
                                  g[y]:=w;
                                  end;
                 end;
l:=1;
repeat
vb:=true;
dfs(l);
for i:=l to n do
if viz[i]=0 then begin
               vb:=false;
               l:=i;
               inc(nc);
               break;
               end;
until vb;
write(h,nc);
close(f);
close(h);
end.