Cod sursa(job #774943)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 6 august 2012 19:18:15
Problema Componente biconexe Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.73 kb
Program biconex;
type lista=^celula;
     celula=record
          nod:longint;
          next:lista;
          end;
     tip=record x,y:longint; end;
var graf,sol:array [1..100001] of lista;
    lev,levmin:array [0..100001] of longint;
    st:array [1..100001] of tip;
    viz,con:array [0..100001] of boolean;
    b1,b2:array [1..1 shl 17] of char;
    i,j,n,m,x,y,nr,vf,aux:longint;
    r,v:lista;
    fi,fo:text;
procedure dfs(nod,nivel,prec:longint);
 var p:lista;
begin
  lev[nod]:=nivel;
  levmin[nod]:=nivel;
  viz[nod]:=true;
  p:=graf[nod];
  while p<>nil do begin
   if viz[p^.nod]=false then begin
    inc(vf);
    st[vf].x:=nod; st[vf].y:=p^.nod;
    dfs(p^.nod,nivel+1,nod);
    if lev[nod]<=levmin[p^.nod] then begin
     inc(nr);
     while (st[vf].x<>nod) and (st[vf].y<>nod) do begin
      new(v); v^.nod:=st[vf].y; v^.next:=sol[nr]; sol[nr]:=v;
      dec(vf);
     end;
     new(v); v^.nod:=st[vf].x; v^.next:=sol[nr]; sol[nr]:=v;
     new(v); v^.nod:=st[vf].y; v^.next:=sol[nr]; sol[nr]:=v;
     dec(vf);
    end;
    if levmin[p^.nod]<levmin[nod] then levmin[nod]:=levmin[p^.nod];
    end
    else if (p^.nod<>prec) and (levmin[p^.nod]<levmin[nod]) then levmin[nod]:=levmin[p^.nod];
  p:=p^.next;
 end;
end;
begin
 assign(fi,'biconex.in');
  assign(fo,'biconex.out');
 settextbuf(fi,b1); settextbuf(fo,b2);
 reset(fi); rewrite(fo); readln(fi,n,m);
 for i:=1 to m do begin
   readln(fi,x,y);
    new(r); r^.nod:=y; r^.next:=graf[x]; graf[x]:=r;
     new(r); r^.nod:=x; r^.next:=graf[y]; graf[y]:=r;
  end;
    dfs(1,1,0);
  writeln(fo,nr);
  for i:=1 to nr do begin
   r:=sol[i];
   while r<>nil do begin write(fo,r^.nod,' '); r:=r^.next; end;
  writeln(fo);
  end;
 close(fo);
end.