Cod sursa(job #556092)

Utilizator chestiaproblema de trimis chestia Data 15 martie 2011 22:17:15
Problema Componente biconexe Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.53 kb
const max_n=100001;
max_m=200001;
type plista=^lista;
lista=record
nod:longint;
urm:plista;
end;
var g:array[0..max_n]of plista;
     u,t,l,nv:array[0..max_n]of longint;
     st:array[0..max_m,0..2]of longint;
     lung,m,n,i,x,y:longint;
     p:plista;
     f,gg:text;

procedure push(i,j:longint);
begin
st[lung,0]:=i;
st[lung,1]:=j;
inc(lung);
end;
procedure pop(var i,j:longint);
begin
dec(lung);
i:=st[lung,0];
j:=st[lung,1];
end;


procedure df(nod:longint);
var p:plista;
x,y:longint;
begin
u[nod]:=1;
p:=g[nod];
l[nod]:=nv[nod];
while p <> nil do begin
      if (p^.nod <> t[nod]) and ( nv[nod]>nv[p^.nod]) then
      push(p^.nod,nod);
      if u[p^.nod] = 0 then begin
         t[p^.nod]:=nod;
         nv[p^.nod]:=nv[nod] + 1;
         df(p^.nod);
         if l[nod] > l[p^.nod] then l[nod]:=l[p^.nod];
         if l[p^.nod] >= nv[nod] then begin
            repeat
            pop(x,y);
            write(gg,'(',x,',',y,')');
            until not((x<>nod) or (y<>nod)) or not((x<>p^.nod) or (y<>nod));
         writeln(gg);
         end;
      end else
      if (p^.nod <> t[nod]) and (l[nod]>nv[p^.nod]) then l[nod]:=nv[p^.nod];
p:=p^.urm;
end;
end;



begin
assign(f,'iulia.in');reset(f);
assign(gg,'iulia.out');rewrite(gg);
readln(f,n,m);
lung:=0;
for i:=1 to n do g[i]:=nil;
for i:=1 to m do begin
readln(f,x,y);
new(p);
p^.nod:=x;
p^.urm:=g[y];
g[y]:=p;
new(p);
p^.nod:=y;
p^.urm:=g[x];
g[x]:=p;
end;
for i:=1 to n do nv[i]:=-1;
nv[1]:=0;
df(1);
close(f);
close(gg);
end.