Cod sursa(job #370793)

Utilizator 05_YohnE1 La5c01 05_Yohn Data 2 decembrie 2009 11:29:51
Problema Componente tare conexe Scor 30
Compilator fpc Status done
Runda Arhiva educationala Marime 1.92 kb
type pnod=^nod;
     nod= record
          info:longint;
          urm:pnod;
          end;

VAR v,tr,sol:array[1..100000]of pnod;
min,pl,gata:array[1..100000]of boolean;
x,y,i,n,m,c,next:longint;

procedure adaug(var p:pnod;x:longint);
var q:pnod;
begin
new(q);
q^.info:=x;
if p=nil then q^.urm:=nil
         else q^.urm:=p;
p:=q;
end;

function caut:longint;
var i:longint;
begin
i:=1;
while (gata[i])and(i<=n)do inc(i);
caut:=i;
end;

procedure plus(x:longint);
var q:pnod;
begin
if not gata[x] then begin
   if not pl[x] then begin
      q:=v[x];
      pl[x]:=true;
      while q<>nil do begin
            plus(q^.info);
            q:=q^.urm;
      end;
   end;
end;
end;

procedure minus(x:longint);
var q:pnod;
begin
if not gata[x] then begin
   if not min[x] then begin
      q:=tr[x];
      min[x]:=true;
      while q<>nil do begin
            minus(q^.info);
            q:=q^.urm;
      end;
   end;
end;
end;

procedure construire_sol;
var i:longint;
begin
for i:=1 to n do if min[i] and pl[i] then begin
                                     gata[i]:=true;
                                     adaug(sol[c],i);
                                     end;
end;


procedure afisare(x:longint);
var q:pnod;
begin
q:=sol[x];
while q<>nil do begin
      write(q^.info,' ');
      q:=q^.urm;
end;
writeln;
end;



BEGIN

assign(input,'ctc.in');reset(input);
assign(output,'ctc.out');rewrite(output);

read(n,m);

for i:=1 to m do begin
    read(x,y);
    adaug(v[x],y);
    adaug(tr[y],x);
end;


next:=1; c:=0;
while next<>n+1 do begin
      fillchar(pl,sizeof(pl),false);
      plus(next);
      fillchar(min,sizeof(min),false);
      minus(next);
      inc(c);
      construire_sol;  {adauga noua solutie si
                       actualizeaza nodurile deja luate}
      next:=caut;
end;

writeln(c);
for i:=1 to c do afisare(i);

close(output);
end.