CRITICAL - Thành phố trọng yếu
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
const
MAXN=20111;
type
list=^node;
node=record
u:longint;
next:list;
end;
procedure add(u:longint; var a:list);
var
p:list;
begin
new(p); p^.u:=u;
p^.next:=a; a:=p;
end;
var
n,m,u,v,cnt,sl:longint;
ke:array[1..MAXN] of list;
res:int64;
w,low,num,reg,father,count:array[1..MAXN] of longint;
procedure dfs1(u:longint);
var
v:longint;
p:list;
begin
reg[u]:=sl; w[u]:=1;
inc(cnt);
low[u]:=cnt; num[u]:=cnt;
p:=ke[u];
while p<>nil do
begin
v:=p^.u; p:=p^.next;
if v=father[u] then continue;
if num[v]=0 then
begin
father[v]:=u;
dfs1(v);
low[u]:=min(low[u],low[v]);
inc(w[u],w[v]);
end
else low[u]:=min(low[u],num[v]);
end;
end;
procedure dfs2(u:longint);
var
v,tmp:longint;
p:list;
begin
p:=ke[u]; tmp:=count[reg[u]]-1;
while p<>nil do
begin
v:=p^.u; p:=p^.next;
if father[v]<>u then continue;
dfs2(v);
//Cac dinh thuoc cay con goc v khong di duoc len tren dinh u
if low[v]>=num[u] then
begin
tmp:=tmp-w[v];
res:=res+int64(w[v])*tmp;
end;
end;
end;
begin
read(n,m);
for m:=1 to m do
begin
read(u,v);
add(u,ke[v]);
add(v,ke[u]);
end;
sl:=0;
for u:=1 to n do
if num[u]=0 then
begin
cnt:=0;
inc(sl);
dfs1(u);
end;
for u:=1 to n do
inc(count[reg[u]]);
for u:=1 to n do
if father[u]=0 then
dfs2(u);
writeln(res/n:0:2);
end.