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;
}

Download