Cod sursa(job #582689)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 15 aprilie 2011 18:24:31
Problema Componente biconexe Scor 46
Compilator fpc Status done
Runda Arhiva educationala Marime 1.63 kb
type muchie=^nod;
     nod=record n:longint; a:muchie; end;

var v:array [1..100000] of muchie;
    chk:array[1..100000] of boolean;
    df, low:array[1..100000] of longint;
    s:array[0..400000] of longint;
    sol:array[1..100000] of muchie;
    m, n, i, x, y, sn, soln:longint;
    p:muchie;
    f, g:text;

function min (a, b:longint):longint;
  begin
  if a>b then min:=b else min := a;
  end;

procedure dfs (k, niv, daddy:longint);
var q:muchie;
  begin
  df[k]:=niv; low[k]:=niv;
  chk[k]:=true;
  q:=v[k];
  while q <> nil do
    begin
    if chk[q^.n]=false then
      begin
      inc(sn); s[sn]:=k; inc(sn); s[sn]:=q^.n;
      dfs(q^.n, niv+1, k);
      if low[q^.n]>=df[k] then
        begin
        inc (soln);
        while (s[sn] <> k) and (sn>0) do
          begin
          new(p); p^.n:=s[sn]; p^.a:=sol[soln]; sol[soln]:=p;
          dec (sn, 2);
          end;
        new(p); p^.n:=s[sn+1]; p^.a:=sol[soln]; sol[soln]:=p;
        end;
      low[k]:=min(low[k], low[q^.n]);
      end
                       else
      begin
      if q^.n<>daddy then low[k]:=min(low[k], df[q^.n]);
      end;
    q:=q^.a;
    end;
  end;

begin
assign (f, 'biconex.in'); reset (f);
assign (g, 'biconex.out'); rewrite (g);

read (f, n, m);
for i := 1 to m do
  begin
  read (f, x, y);
  new(p); p^.n:=y; p^.a:=v[x]; v[x]:=p;
  new(p); p^.n:=x; p^.a:=v[y]; v[y]:=p;
  end;

s[0]:=1;
dfs (1, 1, 0);

writeln (g, soln);
for i := 1 to soln do
  begin
  p:=sol[i];
  while p <> nil do
    begin
    write (g, p^.n, ' ');
    p:=p^.a;
    end;
  writeln (g);
  end;

close (f); close (g);
end.