CRITICAL - Thành phố trọng yếu
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#define MAX 20020
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
typedef long long ll;
vector<int> g[MAX];
int low[MAX];
int num[MAX];
int ncp[MAX];
int nc[MAX];
int sz[MAX];
int n,m,cnt;
ll sp;
void minimize(int &x,const int &y) {
if (x>y) x=y;
}
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
REP(i,m) {
int u,v;
scanf("%d",&u);
scanf("%d",&v);
g[u].push_back(v);
g[v].push_back(u);
}
}
ll sumproduct(const vector<int> &v) {
int sumall=0;
ll sumsqr=0LL;
FORE(it,v) {
sumall+=*it;
sumsqr+=1LL*(*it)*(*it);
}
return (1LL*sumall*sumall-sumsqr)/2;
}
int BFS(int s,int id) {
queue<int> q;
while (!q.empty()) q.pop();
ncp[s]=id;
q.push(s);
int ret=1;
while (!q.empty()) {
int u=q.front();q.pop();
FORE(it,g[u]) if (ncp[*it]==0) {
ncp[*it]=id;
q.push(*it);
ret++;
}
}
return (ret);
}
void visit(int u) {
vector<int> nchild=vector<int>();
int nrest=0;
cnt++;
low[u]=n+7;
num[u]=cnt;
FORE(it,g[u]) {
int v=*it;
if (num[v]==0) {
visit(v);
nc[u]+=nc[v];
if (low[v]>=num[u]) nchild.push_back(nc[v]);
else nrest+=nc[v];
minimize(low[u],low[v]);
}
else minimize(low[u],num[v]);
}
nc[u]++;
nrest+=sz[ncp[u]]-nc[u];
nchild.push_back(nrest);
sp+=sumproduct(nchild);
}
void process(void) {
int tmp=0;
FOR(i,1,n) if (ncp[i]==0) {
tmp++;
sz[tmp]=BFS(i,tmp);
}
FOR(i,1,n) if (num[i]==0) visit(i);
printf("%.2lf",1.0*sp/n);
}
int main(void) {
loadgraph();
process();
return 0;
}