Cod sursa(job #1606743)

Utilizator noi_totinoi toti noi_toti Data 20 februarie 2016 14:53:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.14 kb
program graaf;
const Nmax = 100005;
      Mmax = 200005;
var f, g:text;
    bufin, bufout:array[1..1 shl 16] of byte;
    t:array[0..1, 1..2*Mmax] of longint;
    start:array[1..Nmax] of longint;
    viz:array[1..Nmax] of boolean;
    i, j, k, m, n, conex:longint;
//------------------------
procedure dfs(nod:longint);
var z : longint;
begin
   viz[nod] := true;
   z := start[nod];
   while z <> 0 do
      begin
         if not(viz[t[0, z]]) then dfs(t[0, z]);
         z := t[1, z];
      end;
end;
//--------------------------
begin
   assign(f, 'dfs.in'); reset(f);
   assign(g, 'dfs.out'); rewrite(g);
   settextbuf(f, bufin); settextbuf(g, bufout);
   readln(f, n, m);
   for k := 1 to m do
      begin
         readln(f, i, j);
         t[0, k * 2 - 1] := j;
         t[1, k * 2 - 1] := start[i];
         start[i] := k * 2 - 1;
         t[0, k * 2] := i;
         t[1, k * 2] := start[j];
         start[j] := k * 2;
      end;
   conex := 0;
   for k := 1 to n do
      if not(viz[k]) then
         begin
            inc(conex);
            dfs(k);
         end;
   writeln(g, conex);
   close(f); close(g);
end.