Cod sursa(job #1401224)

Utilizator ursu.daniel2202dUrsu Daniel ursu.daniel2202d Data 25 martie 2015 18:32:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.06 kb
program dfs1;                                //parcurgerea in adancime a unui graf neorientat

var a:array[1..100000] of array of longint;     //lista dinamica de adiacenta
    vizitat:array[1..100000] of byte;
    n,m,i,j,k,x,y:longint;
    f,g:text;

  procedure dfs(x:longint);                           //se viziteaza recursiv toate nodurile conexe

  var i:longint;

  begin

    vizitat[x]:=1;
    for i:=1 to length(a[x])-1 do
      if vizitat[a[x,i]]=0 then dfs(a[x,i]);

  end;

BEGIN

  assign(f,'dfs.in');reset(f);
  readln(f,n,m);

  for i:=1 to n do
    setlength(a[i],1);          //alocare dinamica

  for i:=1 to m do
    begin
      readln(f,x,y);                    //conex. de la nodul x la y
      setlength(a[x],length(a[x])+1);
      a[x,length(a[x])-1]:=y;
      setlength(a[y],length(a[y])+1);
      a[y,length(a[y])-1]:=x;
    end;

  close(f);

  for i:=1 to n do
    if vizitat[i]=0 then
      begin
        inc(k);
        dfs(i);
      end;

  assign(g,'dfs.out');rewrite(g);
  write(g,k);
  close(g);

END.