Cod sursa(job #247681)

Utilizator valytgjiu91stancu vlad valytgjiu91 Data 23 ianuarie 2009 18:28:46
Problema Parcurgere DFS - componente conexe Scor 15
Compilator fpc Status done
Runda Arhiva educationala Marime 1.07 kb
type lista=^elem;
   elem=record
          v:longint;
          adu:lista;
          end;
var f,g:text;
l:array[1..100000] of lista;
ok:boolean;
viz,c:array[1..100000] of longint;
m,nc,s,n,i,x,y,k:longint;
q:lista;
procedure dfs(k:longint);
var p:lista;
begin
viz[k]:=1;
p:=l[k];
while p<>nil do
    if viz[p^.v]=0 then dfs(p^.v)
                 else p:=p^.adu;
end;
begin
assign(f,'dfs.in');
reset(f);
readln(f,n,m);
for i:=1 to m do
  begin
  readln(f,x,y);
  new(q);
  q^.v:=y;
  if l[x]=nil then begin
                   q^.adu:=nil;
                   l[x]:=q;
                   end
                   else
                   begin
                   q^.adu:=l[x];
                   l[x]:=q;
                   end;
  end;
x:=1;
nc:=1;
repeat
         ok:=true;
         dfs(x);
         for i:=1 to n do
             if viz[i]=0 then begin
                ok:=False;
                x:=i;
                nc:=nc+1;
                break;
             end;
   until ok;
assign(g,'dfs.out');
rewrite(g);
writeln(g,nc);
close(g);
end.