#include < cstdio > #include < cstring > #include < algorithm > const int mod = 100019;
int n,
m;
int fa[31],
siz[31];
struct sta {
int x[30];
bool flag;
double val;
void clear() {
memset(x, 0, sizeof(x));
}
void sort() {
std: :sort(x, x + 30);
}
int hashme() {
int v = 0;
for (int i = 29, b = 1; i && x[i]; i--) {
v += x[i] * b;
v %= mod;
b *= 30;
b %= mod;
}
return v;
}
bool operator == (sta b) {
for (int i = 0; i < 30; i++) if (x[i] != b.x[i]) return false;
return true;
}
bool operator != (sta b) {
return * this == b ? false: true;
}
}
st,
hash[mod];
int find(int i) {
return fa[i] == i ? i: fa[i] = find(fa[i]);
}
double gethash(sta st) {
int x = st.hashme();
while (hash[x].flag && hash[x] != st) if (++x == mod) x = 0;
return hash[x] == st ? hash[x].val: -1;
}
double inhash(sta st) {
int x = st.hashme();
while (hash[x].flag) if (++x == mod) x = 0;
hash[x] = st;
hash[x].flag = true;
}
double dp(sta st) {
if (st.hashme() == n) return 0;
double x = gethash(st);
if (x != -1) return x;
double tmp = 0,
ans = 0;
for (int i = 0; i < 30; i++) tmp += st.x[i] * (st.x[i] - 1) / 2;
for (int i = 0; i < 30; i++) for (int j = i + 1; j < 30; j++) {
if (!st.x[i] || !st.x[j]) continue;
sta tmp = st;
tmp.x[i] += tmp.x[j];
tmp.x[j] = 0;
tmp.sort();
ans += st.x[i] * st.x[j] * dp(tmp);
}
ans /= n * (n - 1) / 2;
ans++;
ans /= 1 - tmp / (n * (n - 1) / 2);
st.val = ans;
inhash(st);
return ans;
}
int main() {
int u,
v;
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0; i < mod; ++i) hash[i].flag = false;
for (int i = 1; i <= n; i++) fa[i] = i;
while (m--) {
scanf("%d%d", &u, &v);
fa[find(u)] = find(v);
}
st.clear();
memset(siz, 0, sizeof(siz));
for (int i = 1; i <= n; i++) siz[find(i)]++;
int tot = 0;
for (int i = 1; i <= n; i++) if (siz[i]) st.x[tot++] = siz[i];
st.sort();
printf("%.7lf\n", dp(st));
}
}
来源: http://www.bubuko.com/infodetail-2287464.html