Cod sursa(job #1649696)

Utilizator Stefan.Andras Stefan Stefan. Data 11 martie 2016 14:41:12
Problema Componente tare conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.77 kb
program tareconex;
const Nmax = 100005;
      Mmax = 200005;
var f, g:text;
    t, trans:array[0..1,1..Mmax] of longint;
    start, startrans, top, lung:array[1..Nmax] of longint;
    viz, viztrans:array[1..Nmax] of boolean;
    n, m, k, i, j, contor, ctc:longint;
    sol:array of array of longint;
    bufin, bufout:array[1..1 shl 16] of byte;
procedure df(nod:longint);
var z:longint;
begin
   z := start[nod];
   viz[nod] := true;
   while z <> 0 do
      begin
         if not(viz[t[0, z]]) then df(t[0, z]);
         z := t[1, z];
      end;
   inc(contor);
   top[contor] := nod;
end;

procedure df2(nod:longint);
var z:longint;
begin
   z := startrans[nod];
   //adaug nod la solutie
   inc(lung[ctc]);
   setlength(sol[ctc], lung[ctc] + 1);
   sol[ctc, lung[ctc]] := nod;
   viztrans[nod] := true;
   while z <> 0 do
      begin
         if not(viztrans[trans[0, z]]) then df2(trans[0, z]);
         z := trans[1, z];
      end;
end;

begin
   assign(f, 'ctc.in'); reset(f);
   assign(g, 'ctc.out'); rewrite(g);
   settextbuf(f, bufin); settextbuf(g, bufout);
   readln(f, n, m);
   for k := 1 to m do
      begin
         readln(f, i, j);
         t[0, k] := j;
         t[1, k] := start[i];
         start[i] := k;
         trans[0, k] := i;
         trans[1, k] := startrans[j];
         startrans[j] := k;
      end;

   for i := 1 to n do
      if not(viz[i]) then df(i);

   setlength(sol, n + 1, 1);
   for i := contor downto 1 do
      if not(viztrans[top[i]]) then
         begin
            inc(ctc);
            df2(top[i]);
         end;

   writeln(g, ctc);
   for i := 1 to ctc do
      begin
      for j := 1 to lung[i] do
         write(g, sol[i, j],' ');
      writeln(g);
      end;

   close(f); close(g);
end.