街道赛跑

形式化题目

给定一个有向图 $G = (V, E)$ ，顶点编号为 $0, 1, \dots, N$ 。其中 $0$ 为唯一起点， $N$ 为唯一终点。保证从 $0$ 出发可到达图中所有顶点，且从图中任意顶点均可到达 $N$ ， $N$ 的出度为 $0$ 。

求满足以下条件的两类顶点集合（均不包含 $0$ 和 $N$ ，结果按升序输出）：

不可避免的路口（必经点）：从 $0$ 到 $N$ 的所有有向路径都必须经过的点。即在图中删去该点后，从 $0$ 无法到达 $N$ 。
中间路口（分割点）：属于必经点，且能将图划分为两部分 $C_1$ （起点 $0$ 、终点 $S$ ）和 $C_2$ （起点 $S$ 、终点 $N$ ），满足两部分无公共边，且 $S$ 是两部分的唯一公共点。

正解

思路

这是一道典型的有向图连通性与必经点判定问题。

1. 必经点的判定

对于某个节点 $v \in \{1, 2, \dots, N-1\}$ ：

若要求所有从起点 $0$ 到终点 $N$ 的路径都经过 $v$ ，等价于：若在图中移除顶点 $v$ （禁止访问 $v$ ），从 $0$ 出发遍历图将无法到达 $N$ 。
因此，我们可以枚举每个中间节点 $v$ ，在原图上做一次 BFS 遍历，标记禁止经过 $v$ 。如果终点 $N$ 不在遍历所得的可达点集 $V_0(v)$ 中，则 $v$ 即为一个不可避免的必经点。

2. 分割点的判定

对于第一问中筛选出的必经点 $S$ ：

题目要求将图分成以 $0$ 为起点、 $S$ 为终点的第一部分 $C_1$ ，以及以 $S$ 为起点、 $N$ 为终点的第二部分 $C_2$ 。
两部分无公共边，且 $S$ 为唯一公共点。
考察点集划分：
- 第一部分包含从 $0$ 出发不经过 $S$ 能到达的所有点 $V_0(S)$ ，以及汇合点 $S$ ；
- 第二部分包含从 $S$ 出发能够到达的所有点 $V_S$ 。
若后半部分中存在某个点能够反向走回前半部分，即 $V_0(S) \cap V_S \neq \emptyset$ ，则两部分除了 $S$ 之外还存在其他公共点，甚至产生跨两部分的环路，违反“ $S$ 为唯一公共点”且“第一天以 $S$ 为终点”的定义。
反之，只要 $V_0(S) \cap V_S = \emptyset$ ：
- 前半段不能越过 $S$ 进入后半段（因为 $S$ 是必经点）；
- 后半段不能绕回前半段（因为交集为空）；
- 边集自然被完全划开， $S$ 成为两部分的唯一交汇点。
因此，对于每个必经点 $S$ ，只需从 $S$ 出发再做一次无限制的 BFS 得到 $V_S$ ，判断集合 $V_0(S)$ 与 $V_S$ 是否不相交（即 V_0.isdisjoint(V_S)）即可。

可视化流程

以样例为例，节点之间的划分关系如下：

flowchart LR
    subgraph Part1 [前半段 C1]
        0 --> 1 & 2
        1 --> 3
        2 --> 3
    end
    3((3 <br>中间路口))
    subgraph Part2 [后半段 C2]
        3 --> 4 & 5
        4 --> 6
        5 --> 4 & 9
        6 --> 7 & 8
        7 --> 9
        8 --> 5
    end
    9((9 <br>终点))

在点 $3$ 处，前半段 $\{0, 1, 2\}$ 与后半段 $\{3, 4, 5, 6, 7, 8, 9\}$ 无任何交集，因此点 $3$ 是合法的分割点；而在点 $6$ 处，后半段会通过 $8 \to 5$ 走回前面的点 $5$ （点 $5$ 在避开 $6$ 时可由 $0 \to 3 \to 5$ 到达），导致两段点集出现交集，故 $6$ 不是分割点。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
from collections import deque


def reachable_nodes(graph: list[list[int]], start: int, blocked: int | None = None) -> set[int]:
    """求从 start 出发、不经过 blocked 点所能到达的所有点集合。"""
    visited = {start}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v != blocked and v not in visited:
                visited.add(v)
                queue.append(v)
    return visited


def solve() -> None:
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)

    # 构图：第 i 行以 -2 结尾，最后一行以 -1 结尾
    graph: list[list[int]] = []
    while True:
        token = int(next(it))
        if token == -1:
            break
        row: list[int] = []
        while token != -2:
            row.append(token)
            token = int(next(it))
        graph.append(row)

    n = len(graph) - 1  # 终点编号为 N
    candidates = range(1, n)

    # 第一问：删除点 v 后，从 0 无法到达 n
    unavoidable = [v for v in candidates if n not in reachable_nodes(graph, 0, blocked=v)]

    # 第二问：在第一问基础上，后半段从 v 出发能到达的点集与前半段（0 到达的点集）仅交于 {v}
    splitting = [
        v
        for v in unavoidable
        if reachable_nodes(graph, 0, blocked=v).isdisjoint(reachable_nodes(graph, v))
    ]

    print(len(unavoidable), *unavoidable)
    print(len(splitting), *splitting)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-01 07:05
 * update_at: 2026-10-06 11:13
 */
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 55;

int n;                          // 终点编号为 n，起点编号为 0，总点数 n+1
vector<int> g[MAXN];            // g[u] = 从 u 引出的单行道终点列表
bool vis[MAXN];                 // BFS 访问标记
bool unavoidable[MAXN];         // unavoidable[v] = v 是否为必经点
bool splitting[MAXN];           // splitting[v] = v 是否为中间路口（分割点）

// 从 start 出发、不经过 blocked 点的 BFS，返回 N 是否可达；
// 同时把访问到的点记在 mark[] 里（mark 为 NULL 时只判可达）
bool bfs_reach(int start, int blocked, bool *mark) {
    bool inq[MAXN] = { false };
    queue<int> q;
    q.push(start);
    inq[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (mark != NULL) mark[u] = true;
        for (int i = 0; i < (int)g[u].size(); ++i) {
            int v = g[u][i];
            if (v == blocked || inq[v]) continue; // 删点即禁止经过 blocked
            inq[v] = true;
            q.push(v);
        }
    }
    return inq[n];
}

// 判断 a、b 两个点集是否相交（点集用 bool 数组表示）
bool has_intersection(bool *a, bool *b) {
    for (int i = 0; i <= n; ++i)
        if (a[i] && b[i]) return true;
    return false;
}

int main() {
    // 读入：每行是以 -2 结尾的街道列表，最后一行只有 -1
    int from = 0;
    while (true) {
        int x;
        scanf("%d", &x);
        if (x == -1) break;
        if (x == -2) { ++from; continue; }
        g[from].push_back(x);
    }
    n = from - 1; // from 最后停在终点所在行号，即 N

    // 第一问：删去 v 后 0 无法到达 n，则 v 是不可避免的路口
    for (int v = 1; v < n; ++v)
        if (!bfs_reach(0, v, NULL)) unavoidable[v] = true;

    // 第二问：v 是必经点，且 0 避开 v 的可达集与 v 的可达集不相交
    bool reach0[MAXN], reachS[MAXN];
    for (int v = 1; v < n; ++v) {
        if (!unavoidable[v]) continue;
        for (int i = 0; i <= n; ++i) { reach0[i] = false; reachS[i] = false; }
        bfs_reach(0, v, reach0); // 前半段：从 0 出发不经过 v 能到的点
        bfs_reach(v, -1, reachS); // 后半段：从 v 出发无限制能到的点
        // 两集合除 v 外无公共点（v 不在 reach0 中），即唯一公共点是 v
        if (!has_intersection(reach0, reachS)) splitting[v] = true;
    }

    // 输出两行：先数量，再按升序的点编号
    int cnt = 0;
    for (int v = 1; v < n; ++v) if (unavoidable[v]) ++cnt;
    printf("%d", cnt);
    for (int v = 1; v < n; ++v) if (unavoidable[v]) { printf(" %d", v); }
    printf("\n");

    cnt = 0;
    for (int v = 1; v < n; ++v) if (splitting[v]) ++cnt;
    printf("%d", cnt);
    for (int v = 1; v < n; ++v) if (splitting[v]) { printf(" %d", v); }
    printf("\n");
    return 0;
}

复杂度

时间复杂度：
- 点数 $N \le 50$ ，边数 $M \le 100$ 。
- 枚举每个点 $v \in [1, N-1]$ 执行一次删点 BFS，耗时 $O(N + M)$ 。
- 对满足条件的必经点执行正向 BFS 并计算集合交集，单次耗时 $O(N + M)$ 。
- 总时间复杂度为 $O(N(N + M))$ ，对于给定数据规模约几千次操作，耗时极短（远小于 1 秒）。
空间复杂度：
- 图的邻接表存储开销为 $O(N + M)$ ，BFS 队列与访问集合占用 $O(N)$ 。
- 总空间复杂度为 $O(N + M)$ 。

总结

必经点判定：利用“删点后起点与终点不连通”的等价性质，转化为单次图遍历。
分割点判定：利用“两段除了割点外互不相交”的性质，通过判断 $0$ （避开 $S$ ）可达集与 $S$ 可达集的交集是否为空，极简且严谨地完成了验证。

目录

形式化题目

正解

思路

1. 必经点的判定

2. 分割点的判定

可视化流程

代码

复杂度

总结