Cod sursa(job #408582)

Utilizator hungntnktpHungntnktp hungntnktp Data 3 martie 2010 09:26:01
Problema Componente tare conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.81 kb
{DINH QUANG DAT TIN 07-10}
{CTC}
CONST
 TFI='ctc.in';
 TFO='ctc.out';
 MAX=100001;
TYPE
 arr1int=array[0..MAX] of longint;
 pnode = ^node;
 node = record
         v:longint;
         next:pnode;
        end;
VAR
 fi,fo:text;
 cnt,top,k,mm,m,n:longint;
 ke:array[0..MAX] of pnode;
 d,st,low,num,stack:arr1int;
 free:array[0..MAX] of boolean;

PROCEDURE       add(u,v:longint);
var
 t:pnode;
begin
 new(t);
 t^.v:=v;
 t^.next:=ke[u];
 ke[u]:=t;
end;

PROCEDURE       input;
var
 i,u,v:longint;
begin
 assign(fi,tfi);reset(fi);
  read(fi,n,m);
  for i:= 1 to m do
   begin
    read(fi,u,v);
    add(u,v);
   end;
 close(fi);
end;

PROCEDURE       init;
begin
 fillchar(free,sizeof(free),true);
end;

PROCEDURE       push(u:longint);
begin
 inc(top);
 stack[top]:=u;
end;

PROCEDURE       dfs(u:longint);
var
 v:longint;
 t:pnode;
begin
 t:=ke[u];
 inc(cnt);
 low[u]:=cnt;
 num[u]:=cnt;
 push(u);
 while t<>nil do
  begin
   v:=t^.v;
   t:=t^.next;
   if free[v] then
    begin
     if num[v]=0 then
      begin
       dfs(v);
       if low[u]>low[v] then low[u]:=low[v];
      end
       else if num[v]<low[u] then low[u]:=num[v];
    end;
  end;
 if low[u]=num[u] then
  begin
   inc(mm);
   st[mm]:=k+1;
   v:=0;
   while u<>v do
    begin
     v:=stack[top];
     dec(top);
     inc(k);
     d[k]:=v;
     free[v]:=false;
    end;
  end;
end;

PROCEDURE       process;
var
 i:longint;
begin
 for i:= 1 to n do
  if num[i]=0 then dfs(i);
 st[mm+1]:=n+1;
end;

PROCEDURE       output;
var
 i,j:longint;
begin
 assign(fo,tfo);rewrite(fo);
  writeln(fo,mm);
  for i:= 1 to mm do
   begin
    for j:= st[i]  to st[i+1]-1 do
     write(fo,d[j],' ');
    writeln(fo);
   end;
 close(fo);
end;

BEGIN
 input;
 init;
 process;
 output;
END.