CRITICAL - Thành phố trọng yếu
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
const int N = 20000 + 5, INF = 1000000000;
vector<vector<int> > g;
int n, m, d[N], low[N], r[N], timed;
bool vst[N];
void enter() {
scanf("%d%d",&n,&m); g.resize(n);
for(int i = 0; i < m; ++i) {
int u, v; scanf("%d%d",&u,&v);
g[--u].push_back(--v);
g[v].push_back(u);
}
}
int sqr(const int &x) { return x * x; }
long long res;
void dfs(int u, int p, int nnode) {
d[u] = ++timed; r[u] = 1; low[u] = INF;
int rem = nnode - 1, add = sqr(nnode - 1), nchild = 0;
TR(g[u], it) {
int v = *it;
if(d[v]) { if(v != p) low[u] = min(low[u], d[v]); }
else {
dfs(v, u, nnode); low[u] = min(low[u], low[v]);
r[u] += r[v]; ++nchild;
if((p == -1 && nchild > 1 || p != -1) && low[v] >= d[u])
rem -= r[v], add -= sqr(r[v]);
}
}
if(p == -1 && nchild > 1) rem -= r[g[u][0]], add -= sqr(r[g[u][0]]);
res += add - sqr(rem);
}
int bfs(int u) {
int res = 0; queue<int> q; q.push(u); vst[u] = 1;
while(!q.empty()) {
int u = q.front(); q.pop(); ++res;
TR(g[u], v) if(vst[*v] == 0) vst[*v] = 1, q.push(*v);
}
return res;
}
void solve() {
for(int u = 0; u < n; ++u) if(vst[u] == 0) dfs(u, -1, bfs(u));
printf("%.2lf\n", (double) res / (2*n));
}
int main() {
enter();
solve();
return 0;
}