传送门：洛谷 [[AGC049A] Erasing Vertices](https://www.luogu.com.cn/problem/AT_agc049_a) | AtCoder A - Erasing Vertices

更佳的阅读体验：AGC049A 题解

简要题意：$n$ 个点的简单有向图。重复等概率随机选定一个还未删除的点，删除它和它能到达的点，直到图中没有任何未被删除的点。求期望进行多少次操作后会把图删完。

首先来考虑每个点被删掉的概率。

对于 $x$ 还未被删除时的任意一次操作，如果随到了 $x$，则 $x$ 被选中，如果随到了能到达 $x$ 的其它点，则 $x$ 不可能被选中，否则继续选点。由此过程可知，设 $f_x$ 为能到达 $x$ 的点数（包括 $x$ 本身），则 $x$ 被选中的概率为 $\dfrac{1}{f_x}$ 。

我们知道，期望是线性函数。因此，直接暴力计算出每个点的 $f_i$，答案即为 $\sum \limits_{i = 1}^{n} f_i$。

#include <iostream>
#include <bitset>
using namespace std;

const int N = 110;
int n, f[N];
char c;
bitset<N> g[N], vis;
double ans;

void dfs(int u) {
    if (vis[u]) return;
    ++f[u], vis.set(u);
    for (int i = 1; i <= n; ++i) if (g[u][i]) dfs(i);
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) cin >> c, g[i].set(j, c == '1');
    for (int i = 1; i <= n; ++i) vis.reset(), dfs(i);
    for (int i = 1; i <= n; ++i) ans += 1.0 / f[i];
    cout.precision(12);
    cout << fixed << ans << '\n';
    return 0;
}