Cod sursa(job #774712)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 6 august 2012 14:03:57
Problema Componente biconexe Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.42 kb
Program biconex;
type lista=^celula;
     celula=record
          nod:longint;
          next:lista;
          end;
var graf,sol:array [1..100001] of lista;
    st,lev:array [0..100001] of longint;
    viz:array [0..100001] of boolean;
    i,j,n,m,x,y,nr:longint;
    r,v:lista;
    fi,fo:text;
procedure dfs(nod,nivel,prec:longint);
 var p:lista;
begin
 p:=graf[nod]; viz[nod]:=true; lev[nod]:=nivel;  st[nivel]:=nod;
 while p<>nil do begin
  if viz[p^.nod]=false then dfs(p^.nod,nivel+1,nod)
   else if (lev[p^.nod]<lev[nod]) and (p^.nod<>prec) then lev[nod]:=lev[p^.nod];
  p:=p^.next;
 end;
 new(v); v^.nod:=st[nivel]; v^.next:=r; r:=v;
 if lev[st[nivel-1]]<=lev[st[nivel]] then begin
                                   inc(nr); new(sol[nr]); sol[nr]^.nod:=st[nivel-1];
                                   sol[nr]^.next:=r;
                                   r:=nil;
                                   end
 else lev[st[nivel-1]]:=lev[st[nivel]];
end;
begin
 assign(fi,'biconex.in');
  assign(fo,'biconex.out');
 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;
  r:=nil;  dfs(1,1,0);
  writeln(fo,nr-1);
  for i:=1 to nr-1 do begin
   r:=sol[i];
   while r<>nil do begin write(fo,r^.nod,' '); r:=r^.next; end;
  writeln(fo);
  end;
 close(fo);
end.