Cod sursa(job #708335)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 6 martie 2012 18:50:36
Problema Componente biconexe Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 1.92 kb
type muchie=^nod;
     nod=record n:longint; a:muchie; end;
     much=record s, d:longint; end;

var v:array[1..100000] of muchie;
    st:array[1..200000] of much;
    low, df:array[1..100000] of longint;
    sol:array[1..100000] of muchie;
    viz:array [1..100000] of boolean;
    i, j, n, m, x, y, sn, t:longint;
    p:muchie;
    f, g:text;
    buf1, buf2:array [1.. 1 shl 17] of char;

function min(fx, fy:longint):longint; begin if fx<fy then min:=fx else min :=fy; end;

procedure dfs (fx, niv, tat:longint);
var fq:muchie; fxx, fyy:longint;
  begin
  viz[fx]:=true;
  df[fx]:=niv; low[fx]:=niv;

  fq:=v[fx];
  while fq<> nil do
    begin
    if viz[fq^.n]=false then
      begin
      inc (sn);
      st[sn].s:=fx; st[sn].d:=fq^.n;

      dfs (fq^.n, niv+1, fx);

      low[fx]:=min(low[fx], low[fq^.n]);

      if df[fx]<=low[fx] then
        begin
        inc (t);
        while (sn>0) and (st[sn].s<>fx) and (st[sn].d<>fx) do
          begin
          new(p); p^.n:=st[sn].d; p^.a:=sol[t]; sol[t]:=p;
          dec (sn);
          end;

        new(p); p^.n:=st[sn].d; p^.a:=sol[t]; sol[t]:=p;
        new(p); p^.n:=st[sn].s; p^.a:=sol[t]; sol[t]:=p;
        dec (sn);

        end;

      end
                        else
      begin
      if fq^.n<> tat then low[fx]:=min(low[fx], low[fq^.n]);
      end;


    fq:=fq^.a;
    end;
  end;

begin
assign (f, 'biconex.in'); settextbuf (f, buf1); reset (f);
assign (g, 'biconex.out'); settextbuf (g, buf2); 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;

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

writeln (g, t);
for i := 1 to t 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.