SPOJ-GRAFFDEF King Graffs Defense

King Graffs Defense

tarjan 割边

显然如果是割边的话，边两边的边双连通分量就不能连通

因此考虑 \(dfs\) 搜索树中，计算出所有边双连通分量的大小，然后每个边双连通分量与其他点的乘积之和，就是所有答案情况的 \(\frac{1}{2}\)

总情况数就是 \(\frac{n*(n-1)}{2}\)

记得防止溢出，以及根所在的边双较为特殊，我的代码是没法直接计算他与其他的点的乘积，因此要单独判断加上去

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int head[maxn], nexx[maxn * 10], to[maxn * 10], vp = 1;
ll siz[maxn], cnt[maxn];
int dfn[maxn], low[maxn], tp = 0;
int n, m;

inline void add(int u, int v)
{
    vp++;
    nexx[vp] = head[u];
    to[vp] = v;
    head[u] = vp;
}

void tarjan(int now, int pre)
{
    dfn[now] = low[now] = ++tp;
    siz[now] = 1;
    for(int i=head[now]; i; i=nexx[i])
    {
        int nex = to[i];
        if(dfn[nex] == 0)
        {
            tarjan(nex, i);
            low[now] = min(low[nex], low[now]);
            if(low[nex] > dfn[now])
                cnt[now] += siz[nex] * (n - siz[nex]);
            else
                siz[now] += siz[nex];
        }
        else if(i != (pre ^ 1))
            low[now] = min(low[now], dfn[nex]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0; i<m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    ll tot = (ll)n * (n - 1) / 2;
    ll sum = 0;
    tarjan(1, -1);
    if(cnt[1] != n) sum += siz[1] * (n - siz[1]);
    for(int i=1; i<=n; i++) sum += cnt[i];
    sum /= 2;
    double ans = (double)sum / tot;
    printf("%.5f\n", ans);
    return 0;
}