Cod sursa(job #1366328)

Utilizator mariusadamMarius Adam mariusadam Data 28 februarie 2015 22:43:00
Problema Componente tare conexe Scor 90
Compilator fpc Status done
Runda Arhiva educationala Marime 1.58 kb
program ctce;
var     g,gt,ctc:array of array of longint;
        st:array[1..100000] of longint;
        ng,ngt:array[1..100000] of byte;
        nrc:array[1..80500] of integer;
        viz,vizt:array[1..100000] of 0..1;
        n,m,i,j,k,sol:longint;
        fi,fo:text;

procedure citire;
var i,j,k:longint;
begin
 readln(fi,n,m);
 setlength(g,n+1,1);
 setlength(gt,n+1,1);
 setlength(ctc,n+1,1);
 for k:=1 to m do
 begin
        readln(fi,i,j);
        ng[i]:=ng[i]+1;
        setlength(g[i],ng[i]+1);
        g[i,ng[i]]:=j;
        ngt[j]:=ngt[j]+1;
        setlength(gt[j],ngt[j]+1);
        gt[j,ngt[j]]:=i;
 end;
end;

procedure df(nod:longint);
var i:longint;
begin
 viz[nod]:=1;
 for i:=1 to ng[nod] do
        if viz[g[nod,i]]=0 then
                df(g[nod,i]);
 k:=k+1;
 st[k]:=nod;
end;

procedure dft(nod:longint);
var i:longint;
begin
 vizt[nod]:=1;
 for i:=1 to ngt[nod] do
        if vizt[gt[nod,i]]=0 then
                dft(gt[nod,i]);
 nrc[sol]:=nrc[sol]+1;
 setlength(ctc[sol],nrc[sol]+1);
 ctc[sol,nrc[sol]]:=nod;
end;

begin
 assign(fi,'ctc.in'); reset(fi);
 assign(fo,'ctc.out'); rewrite(fo);
 citire;
 for i:=1 to n do
        if viz[i]=0 then
                df(i);
 //for i:=1 to n do
   //     viz[i]:=0;
 for i:=n downto 1 do
        if vizt[st[i]]=0 then
        begin
                sol:=sol+1;
                dft(st[i]);
        end;
 writeln(fo,sol);
 for i:=1 to sol do
 begin
        for j:=1 to nrc[i] do
                write(fo,ctc[i,j],' ');
        writeln(fo);
 end;
 close(fi);
 close(fo);
end.