Cod sursa(job #288186)

Utilizator punkistBarbulescu Dan punkist Data 25 martie 2009 17:02:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.57 kb
type Lista=^Element;
     Element=record
              nr:longint;
              leg:Lista;
             end;

var n,m,s,k:longint;
    vecini:array[1..100000] of record
                                first,last:Lista;
                               end;
    viz:array[1..100000] of boolean;
    conexe:longint;

procedure Citeste;
var f:text;
    i:longint;
    l,test:Lista;
    a,b:longint;
 begin
  assign(f,'dfs.in');
  reset(f);
  readln(f,n,m);
  for i:=1 to n do
   begin
    New(l);
    l^.nr:=0;
    l^.leg:=nil;
    vecini[i].first:=l;
    vecini[i].last:=l;
   end;
  New(l);
  l^.nr:=0;
  l^.leg:=nil;
  for i:=1 to n do viz[i]:=false;
  for i:=1 to m do
   begin
    readln(f,a,b);
    New(l);
    l^.nr:=b;
    l^.leg:=nil;
    vecini[a].last^.leg:=l;
    vecini[a].last:=l;
    New(l);
    l^.nr:=a;
    l^.leg:=nil;
    vecini[b].last^.leg:=l;
    vecini[b].last:=l;
    end;
  close(f);
 end;

procedure Parcurge(x:longint);
 var l:Lista;
     vecin:longint;
 begin
    viz[x]:=true;
    l:=vecini[x].first;
    repeat
     begin
      vecin:=l^.nr;
      if vecin<>0 then
        if not viz[vecin] then
         begin
          Parcurge(vecin);
         end;
      l:=l^.leg;
     end;
    until l=nil;
  end;


procedure Scrie;
var f:text;
    i,nod:longint;
    l:Lista;
begin
 assign(f,'dfs.out');
 rewrite(f);
 writeln(f,conexe);
 close(f);
end;

begin
Citeste;
conexe:=0;
for k:=1 to n do
 begin
  if not viz[k] then
   begin
    conexe:=conexe+1;
    Parcurge(k);
   end;
 end;
Scrie;
end.