Cod sursa(job #718725)

Utilizator ionutz32Ilie Ionut ionutz32 Data 21 martie 2012 00:43:07
Problema Componente biconexe Scor 46
Compilator fpc Status done
Runda Arhiva educationala Marime 1.96 kb
type ref=^nod;
nod=record
    nr:longint;
    adr:ref;
    end;
var v,comp:array[0..100005] of ref;
viz:array[0..100005] of longint;
st:array[0..100005] of longint;
n,m,i,x,y,d,nrc,nst:longint;
f,g:text;
u:ref;
function df(nod,t:longint):longint;
         var u,u2:ref;
         min,temp:longint;
         begin
         inc(nst);
         st[nst]:=nod;
         inc(d);
         viz[nod]:=d;
         min:=d;
         u:=v[nod];
         while u<>nil do
               begin
               if viz[u^.nr]=0 then
                  begin
                  temp:=df(u^.nr,nod);
                  if temp<min then
                     min:=temp;
                  if temp>=viz[nod] then
                     begin
                     inc(nrc);
                     while st[nst]<>nod do
                           begin
                           new(u2);
                           u2^.nr:=st[nst];
                           u2^.adr:=comp[nrc];
                           comp[nrc]:=u2;
                           dec(nst);
                           end;
                     new(u2);
                     u2^.nr:=nod;
                     u2^.adr:=comp[nrc];
                     comp[nrc]:=u2;
                     end;
                  end
               else
                   if (u^.nr<>t) and (viz[u^.nr]<min) then
                      min:=viz[u^.nr];
               u:=u^.adr;
               end;
         df:=min;
         end;
begin
assign(f,'biconex.in');
assign(g,'biconex.out');
reset(f);rewrite(g);
readln(f,n,m);
for i:=1 to m do
    begin
    readln(f,x,y);
    new(u);
    u^.nr:=y;
    u^.adr:=v[x];
    v[x]:=u;
    new(u);
    u^.nr:=x;
    u^.adr:=v[y];
    v[y]:=u;
    end;
df(1,0);
writeln(g,nrc);
for i:=1 to nrc do
    begin
    u:=comp[i];
    while u<>nil do
          begin
          write(g,u^.nr,' ');
          u:=u^.adr;
          end;
    writeln(g);
    end;
close(f);close(g);
end.