Cod sursa(job #582171)

Utilizator andrei31Andrei Datcu andrei31 Data 14 aprilie 2011 23:21:02
Problema Componente biconexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 2.06 kb
const nmax=100000;
type ref=^nod;
     nod=record
         vf:longword;
         urm:ref;
         end;
var g,cc:Array[1..nmax] of ref;
    l,nv,t:Array[1..nmax] of longint;
    viz,tipar:array[1..nmax] of boolean;
    n,nr,nrs:longword;
    st:Array[1..200000,1..2] of longword;
procedure push(x,y:longword);
begin
inc(nrs);
st[nrs,1]:=x;
st[nrs,2]:=y;
end;

procedure pop(var x,y:longword);
begin
x:=st[nrs,1];y:=st[nrs,2];
dec(nrs);
end;

procedure adaugare2(x,y:longword);
var p:ref;
begin
new(p);
p^.vf:=y;
p^.urm:=cc[x];
cc[x]:=p;
tipar[y]:=true;
end;

procedure df(nod:longword);
var p:ref;
    x,y:longword;
begin
viz[nod]:=true;
l[nod]:=nv[nod];
p:=g[nod];
while p<>nil do
 begin
 if (p^.vf<>t[nod]) and (nv[p^.vf]<nv[nod]) then push(p^.vf,nod);
 if not viz[p^.vf] then
  begin
   viz[p^.vf]:=true;
   t[p^.vf]:=nod;
   nv[p^.vf]:=nv[nod]+1;
   df(p^.vf);
   if l[nod]>l[p^.vf] then l[nod]:=l[p^.vf];
   if l[p^.vf]>=nv[nod]
    then
     begin
      inc(nr);
      fillchar(tipar,sizeof(tipar),false);
      repeat
      pop(x,y);
      if not tipar[y] then adaugare2(nr,y);
      if not tipar[x] then adaugare2(nr,x);
      until ((x=nod) and (y=p^.vf)) or ((x=p^.vf) and (y=nod));
     end;
  end
   else
     if (p^.vf<>t[nod]) and (l[nod]>nv[p^.vf]) then l[nod]:=nv[p^.vf];
 p:=p^.urm;
 end;
end;

procedure adaugare(x,y:longword);
var p:ref;
begin
new(p);
p^.vf:=y;
p^.urm:=g[x];
g[x]:=p;
end;

procedure citire;
var i,m,x,y:longword;
begin
assign(input,'biconex.in');reset(input);
readln(n,m);
for i:=1 to m do
 begin
 readln(x,y);
 adaugare(x,y);
 adaugare(y,x);
 end;
close(input);
end;

procedure afisare;
var i:longword;
    p:ref;
begin
for i:=1 to n do nv[i]:=-1;
for i:=1 to n do if not viz[i] then
 begin
 t[i]:=-1;
 nv[i]:=0;
 df(i);
 end;
assign(output,'biconex.out');rewrite(output);
writeln(nr);
for i:=1 to nr do
 begin
 p:=cc[i];
 while p<>nil do
  begin
  write(p^.vf,' ');
  p:=p^.urm;
  end;
 writeln;
 end;
close(output);
end;


begin
citire;
afisare;
end.