Cod sursa(job #1606748)

Utilizator noi_totinoi toti noi_toti Data 20 februarie 2016 14:57:01
Problema Parcurgere DFS - componente conexe Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 1.29 kb
program dfs;
var viz,t1,t2,start:array of longint;
    f,g:text;
    bufin,bufout:array [1..10000] of char;
    n,m,c,j,st:longint;
    ok:boolean;
  procedure citire;
  var k,l,i,j:longint;
  begin
    assign(f,'dfs.in');reset(f);
    settextbuf(f,bufin);settextbuf(g,bufout);
    k:=0;
    readln(f,n,m);
    setlength(start,n+1);
    setlength(t1,2*m+1);
    setlength(t2,2*m+1);
    setlength(viz,n+1);
    for l:=1 to m do
      begin
        readln(f,i,j);
        inc(k);
        t1[k]:=i;
        t2[k]:=start[j];
        start[j]:=k;
        inc(k);
        t1[k]:=j;
        t2[k]:=start[i];
        start[i]:=k;
      end;
    close(f);
  end;
  procedure df(nod:longint);
  var p:longint;
  begin
    p:=start[nod];
    viz[nod]:=1;
    while p>0 do
      begin
        if viz[t1[p]]=0 then
          viz[t1[p]]:=1;
        p:=t2[p]
      end;
  end;
  procedure afisare;
  begin
    assign(g,'dfs.out');rewrite(g);
    writeln(g,c);
    close(g);
  end;
begin
  citire;
  st:=1;
  c:=0;
  repeat
    ok:=true;
    for j:=st to n do
      begin
        if viz[j]=0 then
          begin
            inc(c);
            df(j);
            st:=j;
            ok:=false;
            break;
          end;
      end;
  until ok=true;
  afisare;
end.