Cod sursa(job #681543)

Utilizator Buzu_Tudor_RoCont vechi Buzu_Tudor_Ro Data 17 februarie 2012 12:19:06
Problema Componente tare conexe Scor 30
Compilator fpc Status done
Runda Arhiva educationala Marime 1.57 kb
Program Depth_First_descompun_in_comp_conexe;
type natural = 0..1;
var fi,fo : text;
    n,i,j,nrc,q,m : longint;
    a:array[0..5000,0..5000] of natural;
    suc,pred:array[0..5000] of longint;

Procedure df_r1(nod:longint);
var k:longint;
begin
      suc[nod]:=nrc;
      for k:=1 to n do if (suc[k]=0) and (a[nod,k]=1) then df_r1(k);
end;

Procedure df_r2(nod:longint);
var k:longint;
begin
     pred[nod]:=nrc;
     for k:=1 to n do if (pred[k]=0) and (a[k,nod]=1) then df_r2(k);
end;
begin
     assign(fi,'ctc.in'); reset(fi);  readln(fi,n,m); nrc:=0;
     assign(fo,'ctc.out'); rewrite(fo);
     for q:=1 to m do begin
                      readln(fi,i,j);
                      a[i,j]:=1;
                      end;

     for i:=1 to n do begin suc[i]:=0; pred[i]:=0; end;

  for i:=1 to n do if suc[i]=0 then begin
                                       nrc:=nrc+1;
                                       df_r1(i); df_r2(i);
                                       for j:=1 to n do if suc[j]<>pred[j] then begin
                                                                                suc[j]:=0;
                                                                                pred[j]:=0;
                                                                                end;
                                       end;
        writeln(fo,nrc);
     for i:=1 to nrc do begin

                        for j:=1 to n do if suc[j]=i then write(fo,j,' ');
                        writeln(fo);
                        end;
     close(fi); close(fo);
 end.