Pagini recente » Cod sursa (job #3205460) | Cod sursa (job #953765) | Cod sursa (job #2160815) | Cod sursa (job #1476246) | Cod sursa (job #402654)
Cod sursa(job #402654)
const infile='biconex.in';
outfile='biconex.out';
maxn=100001;
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.