CRITICAL - Thành phố trọng yếu
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m, cc;
int Time;
int was[N];
int par[N];
int root[N];
int num[N], low[N];
int Size[N];
long long ans[N];
vector<int> a[N];
void dfs(int u) {
was[u] = cc; num[u] = ++Time; low[u] = N; Size[u] = 1;
for (int v : a[u]) if (v != par[u]) {
if (was[v]) {
low[u] = min(low[u], num[v]);
} else {
par[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
Size[u] += Size[v];
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
a[u].push_back(v); a[v].push_back(u);
}
for (int u = 1; u <= n; ++u) {
sort(a[u].begin(), a[u].end());
a[u].resize(unique(a[u].begin(), a[u].end()) - a[u].begin());
}
for (int i = 1; i <= n; ++i) if (!was[i]) {
++cc;
root[cc] = i;
dfs(i);
}
for (int u = 1; u <= n; ++u) {
long long cur = 0, sizePar = Size[root[was[u]]] - 1;
for (int v : a[u]) if (par[v] == u && low[v] >= num[u]) {
ans[u] += cur * Size[v];
cur += Size[v];
sizePar -= Size[v];
}
if (sizePar) {
ans[u] += cur * sizePar;
}
}
long long sum = 0;
for (int u = 1; u <= n; ++u) sum += ans[u];
cout << setprecision(2) << fixed << (long double)sum / n << endl;
return 0;
}