Cod sursa(job #895496)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 27 februarie 2013 11:36:52
Problema Componente tare conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.47 kb
program ctc;
var f,g:text;
    a,b:array of array of longint;
    n,m,i,j,x,y,nr:longint;
    viz,viz1:array[1..100000] of 0..1;
    retine:array[1..100000] of longint;
    nrctc:longint;
    c2:longint;
    bufin,bufout:array[1..65000] of byte;

procedure df (nod:longint);
var i:longint;
begin
 viz[nod]:=1;
 for i:=1 to a[nod,0] do
  if viz[a[nod,i]]=0 then
       df(a[nod,i]);
 inc(nr);
 retine[nr]:=nod;
end;
procedure dfst (nod:longint);
var i:longint;
begin
   viz1[nod]:=1;
   inc(c2);
   setlength(a[nrctc],c2+1);
   a[nrctc,c2]:=nod;
   for i:=1 to b[nod,0] do
    if viz1[b[nod,i]]=0 then
     dfst(b[nod,i]);
end;

begin
 assign (f,'ctc.in'); reset (f);
 assign (g,'ctc.out'); rewrite (G);
 settextbuf (f,bufin);
 settextbuf (g,bufout);
 readln (f,n,m);
 setlength (a,n+1,1);
 setlength(b,n+1,1);
 for i:=1 to m do
 begin
   readln (f,x,y);
   setlength(a[x],length(a[x])+1);
   inc(a[x,0]);
   a[x,a[x,0]]:=y;
   setlength(b[y],length(b[y])+1);
   inc(b[y,0]);
   b[y,b[y,0]]:=x;
 end;
 nr:=0;
 for i:=1 to n do
  if viz[i]=0 then
  begin
   df(i);
  end;
  nrctc:=0;
  for i:=nr downto 1 do
   if viz1[retine[i]]=0 then
   begin
     inc(nrctc);
     setlength(a[nrctc],1);
     a[nrctc,0]:=0;
     c2:=0;
     dfst(retine[i]);
     a[nrctc,0]:=c2;
   end;
   writeln (g,nrctc);
   for i:=1 to nrctc do
   begin
    for j:=1 to a[i,0] do
     write (g,a[i,j],' ');
    writeln(g);
   end;
   close (f); close (G);
end.