Cod sursa(job #402653)

Utilizator nickyyLal Daniel Emanuel nickyy Data 24 februarie 2010 00:30:38
Problema Componente biconexe Scor 24
Compilator fpc Status done
Runda Arhiva educationala Marime 1.89 kb
const infile='biconex.in';
  outfile='biconex.out';
  maxn=100;
type nod=^pnod;
  pnod=record  inf:longint; next:nod; end;
  muchie=record t,f:longint; end;
var a,cb:array[0..maxn]of nod;
  dfn,low:array[0..maxn]of longint;
  s:array[1..maxn]of muchie;
  n,m,nr,vf,ind:longint;

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

 procedure comp(tata,fiu:longint);
 var q:nod;
   p:muchie;
 begin
   inc(nr); p:=s[vf];
   new(q); q^.inf:=p.f; q^.next:=cb[nr]; cb[nr]:=q;
   new(q); q^.inf:=p.t; q^.next:=cb[nr]; cb[nr]:=q;
   dec(vf);
   while(p.t<>tata)or(p.f<>fiu)do begin
     p:=s[vf]; dec(vf);
     new(q); q^.inf:=p.t; q^.next:=cb[nr]; cb[nr]:=q;
     end;
 end;

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

 procedure biconex(u,tu:longint);
 var x:longint;
   q:nod;
 begin
   inc(ind); dfn[u]:=ind; low[u]:=ind;
   q:=a[u];
   while(q<>nil)do begin
     x:=q^.inf;
     if(x<>tu)then
      if(dfn[x]=-1)then begin
        inc(vf); s[vf].f:=x; s[vf].t:=u;
        biconex(x,u);
        low[u]:=min(low[u],low[x]);
        if(low[x]>=dfn[u])then comp(u,x);
        end
      else low[u]:=min(low[u],dfn[x]);
     q:=q^.next;
     end;
 end;

 procedure afisare;
 var i:longint;
   q:nod;
 begin
   ind:=0; nr:=0; vf:=0;
   assign(output,outfile); rewrite(output);
   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 biconex(i,-1);
   writeln(nr);
   for i:=1 to n do begin
     q:=cb[i];
     while(q<>nil)do begin write(q^.inf,' '); q:=q^.next; end;
     writeln;
     end;
   close(output);
 end;

begin
citire; afisare;
end.