Cod sursa(job #1611628)

Utilizator robertadRoxana Rodile robertad Data 24 februarie 2016 12:05:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.39 kb
program liste;
var start:array[1.. 100000] of longint;
    t:array[0..1,1..200000] of longint;
    viz:array[1..100000] of byte;
    n,m,i,j,p,nr:longint;
    f,g:text;
{procedure afisare;
var i,j:longint;
  begin
    writeln(g,'Vectorul start');
    for i:=1 to n do
      write(g,start[i],' ');
    writeln(g);
    writeln(g,'Matricea t');
    for i:=0 to 1 do
      begin
       for j:=1 to p do
         write(g,t[i,j],' ');
       writeln(g);
      end;
  end;  }
procedure dfs(x:longint);
var p:longint;
  begin
    viz[x]:=1;
    {write(g,x,' ');}
    p:=start[x];
    while p<>0 do
      begin
        if viz[t[0,p]]=0 then
                         dfs(t[0,p]);
        p:=t[1,p];
      end;
  end;
procedure citire;
var k:longint;
  begin
    assign(f,'dfs.in');
    assign(g,'dfs.out');
    reset(f);
    rewrite(g);
    readln(f,n,m);
    p:=0;
    for k:=1 to m do
      begin
        readln(f,i,j);
        p:=p+1;
        t[0,p]:= j;
        t[1,p]:=start[i];
        start[i]:=p;
        p:=p+1;
        t[0,p]:=i;
        t[1,p]:=start[j];
        start[j]:=p;
      end;
  end;
begin
  citire;
  for i:=1 to n do
    begin
      if viz[i]=0 then
                  begin
                    dfs(i);
                    {writeln(g);}
                    nr:=nr+1;
                  end;
    end;
  writeln(g,nr);
  close(f);
  close(g);
end.