Cod sursa(job #1365704)

Utilizator mihai1996Toader Mihai mihai1996 Data 28 februarie 2015 14:33:34
Problema Componente tare conexe Scor 60
Compilator fpc Status done
Runda Arhiva educationala Marime 1.5 kb
program componente_tare_conexe;
var s,viz1,viz2,start1,start2:array[1..100000] of longint;
    t1,t2:array[0..1,1..400000] of longint;
    i,j,n,m,x,y,k,nr:longint;
    bufin,bufout:array[1..200010] of byte;

procedure df1(nod:integer);
var p:longint;
begin
  viz1[nod]:=1;
  p:=start1[nod];
  while p<>0 do
    begin
      if viz1[t1[0,p]]=0 then
        df1(t1[0,p]);
      p:=t1[1,p];
    end;
  inc(k);
  s[k]:=nod;
end;


procedure df2(nod,nr:integer);
var p:longint;
begin
  viz2[nod]:=nr;
  p:=start2[nod];
  while p<>0 do
    begin
      if viz2[t2[0,p]]=0 then
        df2(t2[0,p],nr);
      p:=t2[1,p];
    end;
end;

begin
   assign(input,'ctc.in'); reset(input);
   assign(output,'ctc.out'); rewrite(output);
   settextbuf(input,bufin);
   settextbuf(output,bufout);
   readln(n,m);
   k:=0;
   for i:=1 to m do
     begin
       readln(x,y);
       inc(k);
       t1[0,k]:=y;
       t1[1,k]:=start1[x];
       start1[x]:=k;
       t2[0,k]:=x;
       t2[1,k]:=start2[y];
       start2[y]:=k;
     end;

   k:=0;
   for i:=1 to n do
     if viz1[i]=0 then
      df1(i);
   nr:=0;

   {for i:=1 to n do
     write(s[i],' ');
     writeln;    }
   for i:=k downto 1 do
     if viz2[s[i]]=0 then
       begin
         inc(nr);
         df2(s[i],nr);
       end;
   writeln(nr);
   for i:=1 to nr do
     begin
       for j:=1 to n do
         if viz2[j]=i then
           write(j,' ');
       writeln;
     end;
   close(input); close(output);
end.