Cod sursa(job #654700)

Utilizator MihaiBunBunget Mihai MihaiBun Data 30 decembrie 2011 19:55:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 2.11 kb
program kk;
type ref=^inr;
     inr=record
          a:longint;
          adr:ref;
         end;
var f:text;
    v,u:array[1..100000] of ref;
    viz:array[1..100000] of 0..1;
    coco,i,n,m,pc,uc,x,y:longint;
    c:ref;
    cod:array[1..100000] of longint;

begin
  assign(f,'dfs.in');
  reset(f);
  readln(f,n,m);
  for i:=1 to m do
    begin
      readln(f,x,y);
      if v[x]=nil then begin
                         new(c);
                         v[x]:=c;
                         c^.a:=y;
                         c^.adr:=nil;
                         u[x]:=c;
                       end
                  else begin
                        new(c);
                        c^.a:=y;
                        c^.adr:=nil;
                        u[x]^.adr:=c;
                        u[x]:=c;
                       end;
      if v[y]=nil then begin
                         new(c);
                         v[y]:=c;
                         c^.a:=x;
                         c^.adr:=nil;
                         u[y]:=c;
                       end
                  else begin
                        new(c);
                        c^.a:=x;
                        c^.adr:=nil;
                        u[y]^.adr:=c;
                        u[y]:=c;
                       end;
    end;
  coco:=0;
  for i:=1 to n do
   if viz[i]=0 then
     begin
       coco:=coco+1;
       pc:=i;
       uc:=i;
       cod[pc]:=i;
       viz[i]:=1;
       while pc<=uc do
         begin
           c:=v[cod[pc]];
           while c<>nil do begin
                                      if viz[c^.a]=0 then begin
                                                       viz[c^.a]:=1;
                                                       uc:=uc+1;
                                                       cod[uc]:=c^.a;
                                                      end;
                                      c:=c^.adr;
                                end;
           pc:=pc+1;
         end;
     end;
  close(f);
  assign(f,'dfs.out');
  rewrite(f);
  write(f,coco);
  close(f);

end.