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

Download