Pagini recente » Cod sursa (job #3218981) | Cod sursa (job #1807569) | Cod sursa (job #691868) | Cod sursa (job #2134876) | Cod sursa (job #300848)
Cod sursa(job #300848)
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.