洛谷 P4819 杀人游戏
题意
有 \(n\) 个人，他们之中有一个杀手。
每个人都有可能是杀手，并且概率相等。
你可以询问若干人。
若询问的人是杀手，你会被干掉。
若询问的人是平民，你会知道他认识的所有人的身份。
给出一张有向图表示这 \(n\) 个人的关系。
求出你活着知道杀手是谁的概率。
思路
先将原图强连通分量缩点，每个点内的人都互相认识。
形成一张 DAG 后，我们只需要问那些入度为 \(0\) 的点。
问了他们之后，他们后面的点的身份都已知道，不会再有被杀死的风险。
所以概率为 \(1-\frac{k}{n}\)，\(k\) 为入度为 \(0\) 的点的个数，表示问这 \(k\) 个入度为 \(0\) 的点都问不到杀手的概率。
但这还不全对。
如果存在一个点大小为 \(1\)，并且所有出边连的点入度都大于 \(1\)，答案可变为 \(1-\frac{k-1}{n}\)。
因为如果存在这样的点，问过其他点后，他的所有出边连的点身份都清楚了。
如果有杀手，就不用问他了。
如果没有杀手，因为大小为 \(1\)，所以杀手就是他，也不用问他了。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int tot, ver[N << 1], nxt[N << 1], head[N];
int n, m, dfn[N], low[N], in[N];
int cnt, sc, scc[N], stk[N], siz[N], top;
bool instk[N];
vector <int> E[N];
void add(int x, int y) {
ver[++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void tarjan(int x) {
low[x] = dfn[x] = ++ cnt;
stk[++ top] = x; instk[x] = 1;
for (int i = head[x], y; i; i = nxt[i]) {
y = ver[i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (instk[y])
low[x] = min(low[x], dfn[y]);
}
if (low[x] == dfn[x]) {
sc ++;
while (top && stk[top] != x) {
scc[stk[top]] = sc;
instk[stk[top]] = 0;
siz[sc] ++;
top --;
}
scc[stk[top]] = sc;
instk[stk[top]] = 0;
siz[sc] ++;
top --;
}
}
int main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i ++) {
cin >> u >> v;
add(u, v);
}
for (int i = 1; i <= n; i ++) {
if (dfn[i]) continue;
tarjan(i);
}
for (int i = 1; i <= n; i ++)
for (int j = head[i]; j; j = nxt[j])
if (scc[i] != scc[ver[j]]) {
in[scc[ver[j]]] ++;
E[scc[i]].push_back(scc[ver[j]]);
}
double ans = 1, N = n;
int c = 0;
bool flg = 0;
for (int i = 1; i <= sc; i ++) {
if (in[i]) continue;
c ++;
if (siz[c] > 1) continue;
if (flg) continue;
bool ok = 1;
for (auto v : E[i])
if (in[v] <= 1) ok = 0;
if (ok) c --, flg = 1;
}
ans = 1.0 - 1.0 * c / N;
cout << fixed << setprecision(6) << ans << "\n";
return 0;
}