Cod sursa(job #407190)

Utilizator hungntnktpHungntnktp hungntnktp Data 2 martie 2010 09:46:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.22 kb
{DINH QUANG DAT TIN 07-10}
{DFS}
{$ 60000000,0}
CONST
 TFI='dfs.in';
 TFO='dfs.out';
 MAX=100001;
TYPE
 arr1int=array[0..MAX] of longint;
 pnode = ^node;
 node = record
         v:longint;
         next:pnode;
        end;
VAR
 fi,fo:text;
 res,m,n:longint;
 ke:array[0..MAX] of pnode;
 free:array[0..MAX] of boolean;

PROCEDURE       add(u,v:longint);
var
 t:pnode;
begin
 new(t);
 t^.v:=v;
 t^.next:=ke[u];
 ke[u]:=t;
end;

PROCEDURE       input;
var
 u,v,i:longint;
begin
 assign(fi,tfi);reset(fi);
  read(fi,n,m);
  for i:= 1 to m do
   begin
    read(fi,u,v);
    add(u,v);
    add(v,u);
   end;
 close(fi);
end;

PROCEDURE       init;
begin
 fillchar(free,sizeof(free),true);
 res:=0;
end;

PROCEDURE       dfs(u:longint);
var
 t:pnode;
 v:longint;
begin
 t:=ke[u];
 free[u]:=false;
 while t<>nil do
  begin
   v:=t^.v;
   t:=t^.next;
   if free[v] then dfs(v);
  end;
end;

PROCEDURE       process;
var
 i:longint;
begin
 for i:= 1 to n do
  if free[i] then
   begin
    inc(res);
    dfs(i);
   end;
end;

PROCEDURE       output;
begin
 assign(fo,tfo);rewrite(fo);
  writeln(fo,res);
 close(fo);
end;


BEGIN
 input;
 init;
 process;
 output;
END.