Cod sursa(job #1337085)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 8 februarie 2015 16:20:51
Problema Parcurgere DFS - componente conexe Scor 65
Compilator fpc Status done
Runda Arhiva educationala Marime 1.09 kb
Program a1;
type lista = ^nod;
     nod = record
        val : longint;
        next : lista;
     end;
var v:array[1..100009] of lista;
    viz:array[1..100009] of boolean;
    n,m,sol:longint;

procedure add(x,y:longint);
var q:lista;
begin
  new(q);
  q^.val := x;
  q^.next := v[y];
  v[y] := q;
end;

procedure dfs(k:longint);
var q:lista;
begin

   viz[k] := true;
   q := v[k];
   while q <> nil do begin
      if not viz[q^.val] then dfs(q^.val);
      q := q^.next;
   end;
end;

procedure citire;
var i,x,y:longint;
    f:text;
begin
    assign(f,'dfs.in');
    reset(f);
    read(f,n,m);
    for i:=1 to n do viz[i] := false;
    sol := 0;
    for i:=1 to m do begin
       read(f,x,y);
       add(x,y);
       add(y,x);
    end;
    close(f);
end;

procedure solve;
var i:integer;
    g:text;
begin
   assign(g,'dfs.out');
   rewrite(g);
   for i:=1 to n do
      if not viz[i] then begin
          viz[i] := true;
          dfs(i);
          inc(sol);
      end;
   write(g,sol);
   close(g);
end;

Begin
   citire;
   solve;
end.