题目大意
给定一个 $n$ 个点 $m$ 条边的有向无向图，每个点代表一个人，每条单向边代表一组认识关系。已知有一个人是杀手，每个人是杀手的概率都是 $\frac{1}{n}$。有一个警察，每次可以询问一个人，他如果是杀手就会把警察杀掉，如果不是的话他会告诉警察他认识的人中谁是杀手或没有杀手。问警察选择最优策略，查到杀手后还存活的概率。
数据范围：$n \le 10^5, m \le 3 \times 10^5$。
思路分析
首先发现答案等于 $(n - k) / n$，其中 $k$ 表示不知道某人的身份就去查他的次数。然后发现在同一个 SCC 中，我们只需要查一个人即可，并且在缩点后的图中，我们查完一个点就可以查所有它能到达的点。于是，我们统计缩点后的 DAG 度数为 $0$ 的点数即可。
但是有一种特殊情况。因为杀手只有一个，所以在某些情况下我们不需要查完所有点。如果我们查完了 $n - 1$ 个点都是平民，那么剩下的一个点就肯定是杀手。于是我们特判一下，如果缩点后存在一个度数为 $0$ 的点在原图上对应的点数为 $1$，并且它的所有出点的入度都大于 $1$，那么我们就可以不查这个点，也就是将 $k$ 减去一。注意这种操作只能做一次。
这样，我们就解决了这个问题。时间复杂度 $O(n + m)$。这道题告诉我们，一些关于连通性的图论问题往往需要考虑一些特殊情况。
代码实现
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | |
6 | const int maxn = 1e5, maxm = 3e5; |
7 | int n, m, u[maxm + 3], v[maxm + 3], tm, dfn[maxn + 3], low[maxn + 3]; |
8 | int top, st[maxn + 3], cnt, sum[maxn + 3], bel[maxn + 3], deg[maxn + 3]; |
9 | bool in[maxn + 3], ok[maxn + 3]; |
10 | vector<int> G[maxn + 3]; |
11 | |
12 | void add(int u, int v) { |
13 | G[u].push_back(v); |
14 | } |
15 | |
16 | void tarjan(int u) { |
17 | dfn[u] = low[u] = ++tm; |
18 | st[++top] = u, in[u] = true; |
19 | for (int i = 0, v; i < G[u].size(); i++) { |
20 | v = G[u][i]; |
21 | if (!dfn[v]) { |
22 | tarjan(v); |
23 | low[u] = min(low[u], low[v]); |
24 | } else if (in[v]) { |
25 | low[u] = min(low[u], dfn[v]); |
26 | } |
27 | } |
28 | if (dfn[u] == low[u]) { |
29 | ++cnt; |
30 | do { |
31 | sum[cnt]++; |
32 | bel[st[top]] = cnt; |
33 | in[st[top]] = false; |
34 | } while (st[top--] != u); |
35 | } |
36 | } |
37 | |
38 | int main() { |
39 | scanf("%d %d", &n, &m); |
40 | for (int i = 1; i <= m; i++) { |
41 | scanf("%d %d", &u[i], &v[i]); |
42 | add(u[i], v[i]); |
43 | } |
44 | for (int i = 1; i <= n; i++) { |
45 | if (!dfn[i]) { |
46 | tarjan(i); |
47 | } |
48 | } |
49 | for (int i = 1; i <= n; i++) { |
50 | G[i].clear(); |
51 | } |
52 | for (int i = 1; i <= m; i++) { |
53 | if (bel[u[i]] != bel[v[i]]) { |
54 | deg[bel[v[i]]]++; |
55 | G[bel[u[i]]].push_back(bel[v[i]]); |
56 | } |
57 | } |
58 | int ans = 0; |
59 | for (int i = 1; i <= cnt; i++) { |
60 | ans += !deg[i]; |
61 | } |
62 | for (int i = 1; i <= cnt; i++) { |
63 | if (!deg[i] && sum[i] == 1) { |
64 | bool flag = true; |
65 | for (int j = 0; j < G[i].size(); j++) { |
66 | if (deg[G[i][j]] == 1) { |
67 | flag = false; |
68 | break; |
69 | } |
70 | } |
71 | if (flag) { |
72 | ans--; |
73 | break; |
74 | } |
75 | } |
76 | } |
77 | printf("%.6lf\n", 1. * (n - ans) / n); |
78 | return 0; |
79 | } |