Cod sursa(job #407268)

Utilizator hungntnktpHungntnktp hungntnktp Data 2 martie 2010 10:37:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.69 kb
{$M 64000000,0}
{$H-,I-,Q-,R-,S-}
{La Hoang
NGay 2-3-2010
Dem so thanh phan lien thong}
const
   TFI  = 'dfs.in';
   TFO  = 'dfs.out';
   MaxN = 100000;
   MaxM = 200000;
var
   n, m, Res: longint;
   A, Link: array[1..2 * MaxM] of longint;
   H: array[1..MaxN] of longint;
   Free: array[1..MaxN] of boolean;
   (*-----------------------------------*)
   procedure Input;
   var
      fi: text;
      i, u, v: longint;
   begin
      Assign(fi, TFI); Reset(fi);
      Fillchar(H, sizeof(H), 0);
      Readln(fi, n, m);
      for i := 1 to m do
         begin
            Readln(fi, u, v);
            A[i] := v;
            Link[i] := H[u];
            H[u] := i;

            A[i + m] := u;
            Link[i + m] := H[v];
            H[v] := i + m;
         end;
      Close(fi);
   end;
   (*-----------------------------------*)
   procedure Dfs(u: longint);
   var
      i, v: longint;
   begin
      Free[u] := false;
      i := H[u];
      While i <> 0 do
         begin
            v := A[i];
            i := Link[i];
            if Free[v] then Dfs(v);
         end;
   end;
   (*-----------------------------------*)
   procedure Process;
   var
      i: longint;
   begin
      Res := 0;
      Fillchar(Free, sizeof(Free), true);
      for i := 1 to n do
         if Free[i] then
            begin
               inc(Res);
               Dfs(i);
            end;
   end;
   (*-----------------------------------*)
   procedure Output;
   var
      fo: text;
   begin
      Assign(fo, TFO); Rewrite(fo);
      Writeln(fo, Res);
      Close(fo);
   end;
   (*-----------------------------------*)
begin
   Input;
   Process;
   Output;
end.