[中山市选] 杀人游戏

形式化题目

给定有向图 $G=(V,E)$ ， $|V|=N$ 。存在唯一杀手顶点 $k$ （均匀随机分布在 $N$ 个点中）。

警察可询问任意顶点 $u$ ：

若 $u=k$ ，警察被杀，任务失败。
若 $u\neq k$ ，警察安全获得 $u$ 所有直接出邻居的身份信息。

目标：在不询问杀手的前提下，最大化「确定杀手身份」的概率。

一个容易误解的地方：信息是传递的

题面只说「告诉警察他认识的人」，很容易被理解为「警察只能得知 $u$ 的直接出邻居的身份」。但实际含义是：一旦得知某人是平民，就可以继续安全查证那个人，从而获取他的直接出邻居的信息。

例如 $a \to b \to c$ ：

查证 $a$ （是平民）→ 得知 $b$ 的身份。
若 $b$ 也是平民 → 继续查证 $b$ → 得知 $c$ 的身份。
若 $b$ 是杀手 → 已经知道 $b$ 是杀手了，无需查证 $b$ ，但 $c$ 的身份仍未知。

所以信息是沿有向边传递的：虽然 $a$ 不直接「认识」 $c$ ，但通过 $b$ 中转后可以知道 $c$ 的身份。如果只允许直接认识，那除入度为 0 的点以外，其他人的信息永远无法获得，答案恒为 0，显然不合理。

这个传递性正是下文 SCC 建模的基础：同一个强连通分量内互相可达，查证其中任何一个平民即可覆盖整个分量。

正解

思路

本题核心在于信息传递与安全询问的建模。

强连通分量内的信息共享：若 $u,v$ 属于同一 SCC，则从其中任意一个平民出发，都能通过出边安全遍历整个分量。因此每个 SCC 可视为一个「超级节点」，询问一次即可覆盖整个分量。
缩点后形成 DAG：Tarjan 求出所有 SCC 并缩点，得到一张 DAG。信息只能沿拓扑方向单向流动。
必须询问的集合：在 DAG 上，要获知某个 SCC 的身份，必须存在一条从「已询问点」出发的安全路径。对于入度为 0 的 SCC，没有外部安全来源，因此必须直接询问其中任意一个点。记入度为 0 的 SCC 数量为 $cnt$ 。
排除法特例：题目保证恰有一个杀手。若已安全获知 $N-1$ 个人的身份均为平民，则最后一个必然是杀手，无需冒险询问。在缩点语义下，这要求存在一个入度为 0 且 $\text{size}=1$ 的 SCC $S$ ，其所有直接后继 SCC 的入度都 $\ge 2$ （即它们至少还有其他入边来源）。此时 $S$ 可以省略询问：
- 若杀手在其他必须询问的 SCC 中， $S$ 自然是平民。
- 若其他 SCC 均非杀手，则杀手只能是 $S$ 。这种可省略的情况至多发生一次（只有一个杀手），且仅当 $cnt>1$ 时才真正减少必须询问次数。
概率计算：必须冒险询问的次数为 $must$ （初始为 $cnt$ ，可能减 1）。安全概率为 $1 - \dfrac{must}{N}$ 。

代码

正确解法（main.cpp）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 12:51
 * update_at: 2026-10-30 17:50
 */
// P4819 [中山市选] 杀人游戏
// Tarjan 缩点 + DAG 入度统计 + 排除法特例（O(N+M) 正确解法）
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;

int n, m;
vector<int> g[MAXN];           // 有向图邻接表

// Tarjan 缩点
int dfn[MAXN], low[MAXN], timer;
int scc[MAXN], scc_cnt, sz[MAXN];
bool in_stack[MAXN];
vector<int> stk;               // Tarjan 的顶点栈（不是 DFS 调用栈）

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk.push_back(u);
    in_stack[u] = true;

    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    // u 是所在 SCC 的根，弹出整个 SCC
    if (dfn[u] == low[u]) {
        scc_cnt++;
        sz[scc_cnt] = 0;
        while (true) {
            int y = stk.back();
            stk.pop_back();
            in_stack[y] = false;
            scc[y] = scc_cnt;
            sz[scc_cnt]++;
            if (y == u) break;
        }
    }
}

// 缩点后的 DAG
vector<int> dag[MAXN];
int in_deg[MAXN];

// 由 SCC 缩点建 DAG（邻接表去重）
void build_dag() {
    vector<set<int>> temp(scc_cnt + 1);
    for (int u = 1; u <= n; u++) {
        for (int v : g[u]) {
            if (scc[u] != scc[v]) {
                temp[scc[u]].insert(scc[v]);
            }
        }
    }
    for (int i = 1; i <= scc_cnt; i++) {
        dag[i].clear();
        for (int v : temp[i]) {
            dag[i].push_back(v);
        }
    }
}

// 统计 DAG 上每个 SCC 的入度
void calc_in_deg() {
    memset(in_deg, 0, sizeof(int) * (scc_cnt + 1));
    for (int i = 1; i <= scc_cnt; i++) {
        for (int v : dag[i]) {
            in_deg[v]++;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);       // 有向边：x 认识 y
    }

    // Tarjan 缩点
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 缩点建 DAG，统计入度
    build_dag();
    calc_in_deg();

    // 统计入度为 0 的 SCC 数量
    int cnt = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (in_deg[i] == 0) cnt++;
    }

    // 排除法特例：size==1 且入度 0 的 SCC，其所有后继入度 ≥2 即可省略
    // 这是 O(1) 检查，不需要 BFS
    bool can_omit = false;
    for (int i = 1; i <= scc_cnt && !can_omit; i++) {
        if (in_deg[i] == 0 && sz[i] == 1) {
            bool ok = true;
            for (int v : dag[i]) {
                if (in_deg[v] <= 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) can_omit = true;
        }
    }

    // 必须冒险询问的次数
    // 特例：n==1 时不需要任何询问
    int must = (n == 1 ? 0 : cnt);
    if (can_omit && must > 0) must = must - 1;

    // 幸存且确定杀手的概率
    double ans = 1.0 - (double)must / n;
    printf("%.6f\n", ans);

    return 0;
}

TLE 版本（main-tle.cpp）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 12:51
 * update_at: 2026-10-23 22:40
 */
// P4819 [中山市选] 杀人游戏
// Tarjan 缩点 + DAG 入度统计 + 排除法特例
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;

int n, m;
vector<int> g[MAXN];           // 有向图邻接表

// Tarjan 缩点
int dfn[MAXN], low[MAXN], timer;
int scc[MAXN], scc_cnt, sz[MAXN];
bool in_stack[MAXN];
vector<int> stk;               // Tarjan 的顶点栈（不是 DFS 调用栈）

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk.push_back(u);
    in_stack[u] = true;

    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    // u 是所在 SCC 的根，弹出整个 SCC
    if (dfn[u] == low[u]) {
        scc_cnt++;
        sz[scc_cnt] = 0;
        while (true) {
            int y = stk.back();
            stk.pop_back();
            in_stack[y] = false;
            scc[y] = scc_cnt;
            sz[scc_cnt]++;
            if (y == u) break;
        }
    }
}

// 缩点后的 DAG
vector<int> dag[MAXN];
int in_deg[MAXN];

// 由 SCC 缩点建 DAG（邻接表去重）
void build_dag() {
    vector<set<int>> temp(scc_cnt + 1);
    for (int u = 1; u <= n; u++) {
        for (int v : g[u]) {
            if (scc[u] != scc[v]) {
                temp[scc[u]].insert(scc[v]);
            }
        }
    }
    for (int i = 1; i <= scc_cnt; i++) {
        dag[i].clear();
        for (int v : temp[i]) {
            dag[i].push_back(v);
        }
    }
}

// 统计 DAG 上每个 SCC 的入度
void calc_in_deg() {
    memset(in_deg, 0, sizeof(int) * (scc_cnt + 1));
    for (int i = 1; i <= scc_cnt; i++) {
        for (int v : dag[i]) {
            in_deg[v]++;
        }
    }
}

// 判断省略 SCC omit_s 后，未被覆盖的原图节点是否恰好为 1
// 方法：多源 BFS，从除 omit_s 外所有入度 0 的 SCC 出发，统计覆盖节点数
bool can_omit_scc(int omit_s) {
    if (sz[omit_s] != 1) return false;

    vector<bool> vis(scc_cnt + 1, false);
    vector<int> q;
    for (int i = 1; i <= scc_cnt; i++) {
        if (in_deg[i] == 0 && i != omit_s && !vis[i]) {
            vis[i] = true;
            q.push_back(i);
        }
    }
    size_t head = 0;
    while (head < q.size()) {
        int u = q[head++];
        for (int v : dag[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push_back(v);
            }
        }
    }

    int covered = 0;
    for (int node = 1; node <= n; node++) {
        if (vis[scc[node]]) covered++;
    }
    return (n - covered) == 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);       // 有向边：x 认识 y
    }

    // Tarjan 缩点
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 缩点建 DAG，统计入度
    build_dag();
    calc_in_deg();

    // 统计入度为 0 的 SCC 数量
    int cnt = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (in_deg[i] == 0) cnt++;
    }

    // 排除法特例：是否存在 size==1 的入度 0 SCC 可以省略询问
    bool can_omit = false;
    for (int i = 1; i <= scc_cnt && !can_omit; i++) {
        if (in_deg[i] == 0 && can_omit_scc(i)) {
            can_omit = true;
        }
    }

    // 必须冒险询问的次数
    int must = cnt;
    if (can_omit) must = cnt - 1;
    if (must < 0) must = 0;

    // 幸存且确定杀手的概率
    double ans = 1.0 - (double)must / n;
    printf("%.6f\n", ans);

    return 0;
}

TLE 原因分析

main-tle.cpp 中存在一个名为 can_omit_scc(int omit_s) 的函数，其逻辑为：

cpp

1
2
3
4
5bool can_omit_scc(int omit_s) {
    if (sz[omit_s] != 1) return false;
    // ... 多源 BFS 遍历 DAG，统计未被覆盖的节点数
    // ... 遍历全图 n 个节点判断是否恰好剩 1 个
}

每次调用 can_omit_scc 都需要：

从所有入度为 0 且非 omit_s 的 SCC 出发做 BFS，复杂度 $O(N+M)$
遍历全图 n 个节点统计覆盖情况，复杂度 $O(N)$

题目数据范围 $N \le 10^5$ ， $M \le 3\times 10^5$ 。若入度为 0 的 SCC 数量为 $cnt$ ，则总复杂度达到 $O(cnt \times N)$ 。在最坏情况下 $cnt$ 可达 $O(N)$ ，导致 $O(N^2)$ 级别的超时。

正确做法：判断「能否省略询问」只需要 $O(1)$ 检查：

该 SCC 大小是否为 1
其所有直接后继 SCC 的入度是否都 $> 1$

这正是 brute.cpp 和 main.cpp 采用的逻辑，无需任何 BFS 或全图遍历。

复杂度

时间：Tarjan $O(N+M)$ ，建 DAG 与统计 $O(N+M)$ ，总 $O(N+M)$ 。
空间： $O(N+M)$ 。

总结

本题通过 Tarjan 缩点将「询问一个点覆盖整个 SCC」这一性质转化为 DAG 上的「覆盖所有入度为 0 的超级节点」。在此基础上，利用「恰有一个杀手」这一全局约束，识别出可以利用排除法省略询问的 size=1 入度 0 分量，最终得到最优安全概率。算法线性时间，正确性基于 SCC 信息共享与 DAG 拓扑覆盖。