Cod sursa(job #300848)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 7 aprilie 2009 18:46:36
Problema Componente biconexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 3.45 kb
type lista=^element;
     element=record
        i:longint;
        a:lista;
             end;
     rec=record
          x,y:longint;
         end;
var v:array[1..100000] of lista;
    lr,xx,i,n,m,x,y,ls,nr:longint;
    st:array[1..100000] of rec;
    r,viz,l,nv,t:array[1..100000] of longint;
    p:lista;

    sol:array[1..100000] of lista;
procedure pivot(s,d:longint; var mi:longint);
   var ii,jj,pi,pj,aux:longint;
   begin
     ii:=s; jj:=d;
     pi:=0; pj:=1;
     while ii<jj do
        begin
          if r[ii]<r[jj] then
             begin
               aux:=r[ii]; r[ii]:=r[jj]; r[jj]:=aux;
               aux:=pi; pi:=pj;pj:=aux;
             end;
          ii:=ii+pi; jj:=jj-pj;
        end;
     mi:=ii;
   end;
procedure sort(s,d:longint);
   var mi:longint;
   begin
      if s<d then
        begin
          pivot(s,d,mi);
          sort(s,mi); sort(mi+1,d);
        end;
   end;
procedure adaugare(x,y:longint);
  begin
    inc(ls); st[ls].x:=x; st[ls].y:=y;
  end;
procedure df(nod:longint);
    var w,q:lista;
    begin
      viz[nod]:=1;
      l[nod]:=nv[nod];
      w:=v[nod];
      while w<>nil do
        begin
          if (w^.i<>t[nod])and(nv[nod]>nv[w^.i]) then adaugare(w^.i,nod);
          if viz[w^.i]=0 then
              begin
                nv[w^.i]:=nv[nod]+1;
                t[w^.i]:=nod;
                df(w^.i);
                if l[w^.i]<l[nod] then
                   l[nod]:=l[w^.i];
                if nv[nod]<=l[w^.i] then
                   begin
                     inc(nr);  lr:=2;
                     x:=st[ls].x; y:=st[ls].y;xx:=x;
                     {new(q); q^.i:=x; q^.a:=sol[nr]; sol[nr]:=q;
                     new(q); q^.i:=y; q^.a:=sol[nr]; sol[nr]:=q;}
                     r[1]:=x; r[2]:=y;
                     dec(ls);
                     if not(((x=w^.i)and(y=nod))or((x=nod)and(y=w^.i))) then
                     repeat
                       begin
                       x:=st[ls].x; y:=st[ls].y;
                       dec(ls);
                       if y<>xx then begin
                                      { new(q); q^.i:=y; q^.a:=sol[nr]; sol[nr]:=q;} inc(lr); r[lr]:=y;
                                      end;
                       end;
                     until ((x=w^.i)and(y=nod))or((x=nod)and(y=w^.i));
                     sort(1,lr);
                     new(q); q^.i:=r[1]; q^.a:=sol[nr]; sol[nr]:=q;y:=1;
                     for x:=2 to lr do
                       begin
                          if r[x]<>r[y] then
                            begin
                         new(q); q^.i:=r[x]; q^.a:=sol[nr]; sol[nr]:=q;
                         y:=x;
                            end;
                       end;
                   end;
              end
                         else
                            if (w^.i<>t[nod])and(nv[w^.i]<l[nod]) then l[nod]:=nv[w^.i];
          w:=w^.a;
        end;
    end;
begin
assign(input,'biconex.in'); reset(input);
assign(output,'biconex.out'); rewrite(output);
readln(n,m);
for i:=1 to m do
  begin
    readln(x,y);
    new(p);
    p^.i:=y; p^.a:=v[x]; v[x]:=p;
    new(p);
    p^.i:=x; p^.a:=v[y]; v[y]:=p;
  end;
nr:=0;
for i:=1 to n do
  begin
    nv[i]:=1;
    df(i);
  end;
writeln(nr);
for i:=1 to nr do
  begin
    p:=sol[i];
    while p<>nil do
      begin
        write(p^.i, ' '); p:=p^.a;
      end;
    writeln;
  end;
close(output);
close(input);
end.