Cod sursa(job #341941)

Utilizator ionutz32Ilie Ionut ionutz32 Data 19 august 2009 23:41:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.59 kb
type ref=^nod;
nod=record
    nr:longint;
    adr:ref;
    end;
var v:array[1..100000] of ref;
cmp:array[1..100000] of longint;
u,c,sf:ref;
n,m,i,j,k,nrc:longint;
f,g:text;
begin
assign(f,'dfs.in');
assign(g,'dfs.out');
reset(f);rewrite(g);
readln(f,n,m);
for i:=1 to m do
    begin
    readln(f,j,k);
    if v[j]=nil then
       begin
       new(v[j]);
       v[j]^.nr:=k;
       v[j]^.adr:=nil;
       end
    else
        begin
        new(u);
        u^.nr:=k;
        u^.adr:=v[j];
        v[j]:=u;
        end;
    if v[k]=nil then
       begin
       new(v[k]);
       v[k]^.nr:=j;
       v[k]^.adr:=nil;
       end
    else
        begin
        new(u);
        u^.nr:=j;
        u^.adr:=v[k];
        v[k]:=u;
        end;
    end;
for i:=1 to n do
    if cmp[i]=0 then
       begin
       nrc:=nrc+1;
       cmp[i]:=nrc;
       new(c);
       c^.adr:=nil;
       c^.nr:=i;
       sf:=c;
       repeat
             u:=v[c^.nr];
             while u<>nil do
                   begin
                   if cmp[u^.nr]=0 then
                      begin
                      cmp[u^.nr]:=nrc;
                      new(sf^.adr);
                      sf^.adr^.nr:=u^.nr;
                      sf:=sf^.adr;
                      sf^.adr:=nil;
                      end;
                   u:=u^.adr;
                   end;
             if c<>nil then
                begin
                u:=c^.adr;
                dispose(c);
                c:=u;
                end;
       until c=nil;
       end;
write(g,nrc);
close(f);close(g);
end.