Cod sursa(job #407277)

Utilizator saodem74hieu tran saodem74 Data 2 martie 2010 10:41:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.11 kb
const tfi='dfs.in';
      tfo='dfs.out';
      maxn=100100;
type  li=record
          u,v:longint;
        end;
var   fi,fo:text;
      res,n,m:longint;
      dd,st,ke:array[0..maxn*2] of longint;
      ds:array[0..maxn] of li;

procedure enter;
var i:longint;
begin
  read(fi,n,m);
  for i:=1 to m do
   with ds[i] do
    begin
     read(fi,u,v);
     inc(st[u]);
     inc(st[v]);
    end;
   inc(st[1]);
   for i:=2 to n+1 do st[i]:=st[i]+st[i-1];
   for i:=1 to m do
    with ds[i] do
     begin
      dec(st[u]); ke[st[u]]:=v;
      dec(st[v]); ke[st[v]]:=u;
     end;
end;

       procedure dfs(u:longint);
       var  v:longint;
       begin
       dd[u]:=1;
        for v:=st[u] to st[u+1]-1 do
         if dd[ke[v]]=0 then
           dfs(ke[v]);
       end;

procedure process;
var i,j:longint;
begin
  for i:=1 to n do
   if dd[i]=0 then
    begin
     inc(res);
     dfs(i);
    end;
    writeln(fo,res);
end;

procedure print;
begin
end;

begin
  assign(fi,tfi); reset(fi);
  assign(fo,tfo); rewrite(fo);
  enter;
  process;
  print;
  close(fi); close(fo);
end.