Cod sursa(job #280342)

Utilizator valytgjiu91stancu vlad valytgjiu91 Data 13 martie 2009 12:30:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.33 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
begin
    if viz[p^.v]=0 then dfs(p^.v);
p:=p^.adu;
end;
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;
  new(q);
  q^.v:=x;
  if l[y]=nil then begin
                   q^.adu:=nil;
                   l[y]:=q;
                   end
                   else
                   begin
                   q^.adu:=l[y];
                   l[y]:=q;
                   end;

  end;
x:=1;
nc:=1;
repeat
         ok:=true;
         dfs(x);
         for i:=x 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.