GRAPH_ - Tìm khớp và cầu (Cơ bản)
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
var n,m,i,j,cnt,cau,khop:longint;
p,low,num,cha,con:array[1..10010] of longint;
a,b,c:array[1..100010] of longint;
d:array[1..10010] of boolean;
procedure visit(x,y:longint);
var i:longint;
begin
inc(cnt); num[x]:=cnt; low[x]:=cnt;
cha[x]:=y;
for i:=p[x]+1 to p[x+1] do
if a[i]<>y then
begin
if num[a[i]]>0 then low[x]:=min(low[x],num[a[i]])
else
begin
visit(a[i],x);
low[x]:=min(low[x],low[a[i]]);
end;
end;
end;
begin
read(n,m);
for i:=1 to m do
begin
read(b[i],c[i]);
inc(p[b[i]]);
inc(p[c[i]]);
end;
for i:=2 to n+1 do inc(p[i],p[i-1]);
for i:=1 to m do
begin
a[p[b[i]]]:=c[i];
dec(p[b[i]]);
a[p[c[i]]]:=b[i];
dec(p[c[i]]);
end;
for i:=1 to n do
if cha[i]=0 then visit(i,-1);
for i:=1 to n do
if cha[i]>0 then inc(con[cha[i]]);
for i:=1 to n do
begin
j:=cha[i];
if j<0 then continue;
if low[i]>=num[i] then inc(cau);
if d[j] then continue;
if (low[i]>=num[j]) and ((cha[j]<>-1) or (con[j]>1)) then
begin
d[j]:=true; inc(khop);
end;
end;
writeln(khop,' ',cau);
end.