Cod sursa(job #282298)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 17 martie 2009 12:23:02
Problema Componente biconexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 2.07 kb
type
    adresa = ^nod;
    nod = record inf: longint; adr: adresa; end;

const
    dim = 100000;

var
    n,m,i,j,x,y,lst,nrsol:longint;
    a,sol: array[1..dim] of adresa;
    low:array[1..dim] of longint;
    df :array[1..dim] of longint;
    st: array[1..dim*2] of longint;
    viz: array[1..dim] of byte;
    f : text;
    q : adresa;

function min(x,y:longint):longint;
begin
if(x<=y) then min:=x else min:=y;
end;


procedure update(x,y: longint);
var xx,yy: longint;
    q: adresa;
begin
inc(nrsol);
repeat
xx := st[lst];
yy := st[lst-1];
new(q); q^.inf:=xx; q^.adr:=sol[nrsol]; sol[nrsol]:=q;
new(q); q^.inf:=yy; q^.adr:=sol[nrsol]; sol[nrsol]:=q;
dec(lst,2);
until (yy=x) and (xx=y);
end;


procedure parc (k,niv,tata: longint);
var
   q: adresa;
begin
viz[k]:=1;
df[k]:=niv; low[k]:=niv;
q:=a[k];
while (q<>nil) do
      begin
      if (tata<>q^.inf) then
         begin
         if (viz[q^.inf] = 0) then
            begin
            inc(lst); st[lst] := k;
            inc(lst); st[lst] := q^.inf;
            parc(q^.inf, niv+1, k);
            if (low[q^.inf] >= df[k]) then
               update(k, q^.inf);
            low[k]:=min(low[k], low[q^.inf]);
            end
         else
            begin
            low[k]:=min(low[k],df[q^.inf]);
            end;
         end;
      q:=q^.adr;
      end;
end;

begin
assign (f,'biconex.in');
reset (f);
readln(f, n, m);
for i:=1 to m do
    begin
    readln (f, x, y);
    new (q); q^.inf := x; q^.adr := a[y]; a[y] := q;
    new (q); q^.inf := y; q^.adr := a[x]; a[x] := q;
    end;
close (f);

lst:=0;
for i:=1 to n do
    if viz[i] = 0 then
       parc(i,1,0);

assign(f,'biconex.out');
rewrite(f);
writeln(f, nrsol);
for i:=1 to nrsol do
    begin
    fillchar(viz,sizeof(viz),0);
    q:=sol[i];
    while (q<>nil) do
          begin
          if viz[q^.inf] = 0 then
             begin
             viz[q^.inf]:=1;
             write(f, q^.inf,' ');
             end;
          q:=q^.adr;
          end;
    writeln(f);
    end;
close(f);

end.