Cod sursa(job #402459)

Utilizator nickyyLal Daniel Emanuel nickyy Data 23 februarie 2010 21:19:58
Problema Componente tare conexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.62 kb
const infile='ctc.in';
  outfile='ctc.out';
  maxn=100001;
type nod=^pnod;
  pnod=record  inf:longint; next:nod; end;
var a,c:array[0..maxn]of nod;
  uz:array[0..maxn]of byte;
  dfn,low,s:array[0..maxn]of longint;
  n,nr,m,ind,vf:longint;

 procedure citire;
 var i,j:longint;
   p:nod;
 begin
   assign(input,infile); reset(input); readln(n,m);
   while(m>0)do begin
     readln(i,j); dec(m);
     new(p); p^.inf:=j; p^.next:=a[i]; a[i]:=p;
     end;
   close(input);
 end;

 function min(x,y:longint):longint;
 begin
   if(x>y)then min:=y
   else min:=x;
 end;

 procedure Tarjan(x:longint);
 var p:nod;
   y:longint;
 begin
   dfn[x]:=ind; low[x]:=ind; inc(ind);
   inc(vf); s[vf]:=x; uz[x]:=1;
   p:=a[x];
   while(p<>nil)do begin
     if(dfn[p^.inf]=-1)then begin
       Tarjan(p^.inf); low[x]:=min(low[x],low[p^.inf]);
       end
     else if(uz[p^.inf]=1)then low[x]:=min(low[x],low[p^.inf]);
     p:=p^.next;
     end;
   if(low[x]=dfn[x])then begin
     inc(nr);
     repeat
       y:=s[vf]; dec(vf); uz[y]:=0;
       new(p); p^.inf:=y; p^.next:=c[nr]; c[nr]:=p;
     until y=x;
     end;
 end;

 procedure solve;
 var i:longint;
 begin
   ind:=0; vf:=0; nr:=0;
   for i:=1 to n do begin dfn[i]:=-1; low[i]:=-1; end;
   for i:=1 to n do if(dfn[i]=-1)then tarjan(i);
 end;

 procedure afisare;
 var i:longint;
  p:nod;
 begin
   assign(output,outfile); rewrite(output); writeln(nr);
   for i:=1 to nr do  begin
     p:=c[i];
     while(p<>nil)do begin write(p^.inf,' '); p:=p^.next; end;
     writeln;
     end;
   close(output);
 end;

begin
citire; solve; afisare;
end.