Cod sursa(job #493938)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 19 octombrie 2010 22:54:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.98 kb
program dfs;
const maxn=100001;
      maxm=200001;
type inod=0..maxn;
     pnod=^nod;
     nod=record
     inf:inod;
     next:pnod;
     end;
var f,g:text; A,ult:array[inod] of pnod; i,n,S:inod; m:0..maxm;
    viz:array[inod] of 0..1;
procedure add(x,y:inod);   {face legatura x->y}
var q:pnod;
begin
new(q);
q^.inf:=y;
q^.next:=nil;
If A[x]=nil then begin A[x]:=q; ult[x]:=A[x]; end
            else begin ult[x]^.next:=q; ult[x]:=q; end;
end;
procedure citire;
var x,y:inod;
begin
Readln(f,n,m);
For i:=1 to m do
 begin
 Readln(f,x,y);
 add(x,y);
 add(y,x);
 end;
end;
procedure dfs(p:inod);
var x:pnod;
begin
viz[p]:=1; Writeln(p);
x:=A[p];
While x<>nil do
 begin
 If viz[x^.inf]=0 then dfs(x^.inf);
 x:=x^.next;
 end;
end;
begin
Assign(f,'dfs.in'); Reset(f);
Assign(g,'dfs.out');Rewrite(g);
citire; Close(f);
For i:=1 to n do viz[i]:=0;
S:=0;
For i:=1 to n do
 If viz[i]=0 then
  begin
  inc(S);
  dfs(i);
  end;
Write(g,S); Close(g);
end.