「一本通 3.6 练习 2」嗅探器

题目描述

红军要监听蓝军两个信息中心之间交换的所有信息，嗅探器必须装在一台「中间服务器」上，使得任意一条从 $a$ 到 $b$ 的路径都经过它。输入第一行是服务器数 $n$ （ $1 \leqslant n \leqslant 100$ ），接下来若干行每行两个整数 $i, j$ 表示 $i, j$ 之间有双向连接，以 0 0 结束，最后一行是两个信息中心 $a, b$ 。输出编号最小的合法服务器编号，无解输出 No solution。样例中 $a=4, b=2$ ，输出 1。

思路

点 $v$ 是 $a$ 到 $b$ 的必经点，当且仅当删掉 $v$ 后 $a$ 到不了 $b$ 。于是从 1 到 $n$ 枚举候选点（跳过 $a$ 、 $b$ 自身），每个点删掉后做一次 DFS 判连通，第一个使 $a$ 、 $b$ 不连通的就是答案； $n \leqslant 100$ ，总复杂度 $O(n(n+m))$ 。

参考代码

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#!/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-09-30 15:55
# update_at: 2026-09-30 15:55

import sys

NO_ANSWER = "No solution"  # 找不到必经点时的输出


def reachable(g: list[set[int]], src: int, dst: int, skip: int) -> bool:
    """删掉顶点 skip 后，src 是否还能到达 dst（显式栈 DFS）。"""
    seen = {skip}  # 把 skip 预置为已访问，等于从图中删掉它
    stack = [src]
    while stack:
        v = stack.pop()
        if v == dst:
            return True
        seen.add(v)
        stack += [w for w in g[v] if w not in seen]
    return False


def find_sniffer(g: list[set[int]], n: int, a: int, b: int) -> int | None:
    """编号最小的中间服务器 v：a 到 b 的每条路径都必经 v；不存在则返回 None。"""
    # v 在所有 a-b 路径上 ⟺ 删掉 v 后 a 到不了 b（割点判定）。
    # 逐点删一次再测连通即可；v 不能是 a、b 自身，它们不是"中间"服务器。
    for v in range(1, n + 1):
        if v != a and v != b and not reachable(g, a, b, v):
            return v
    return None


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 服务器数目
    g: list[set[int]] = [set() for _ in range(n + 1)]
    while True:
        i, j = next(data), next(data)
        if i == 0 and j == 0:  # 0 0 标志拓扑描述结束
            break
        g[i].add(j)
        g[j].add(i)  # 连接是双向的
    a, b = next(data), next(data)  # 两个信息中心

    ans = find_sniffer(g, n, a, b)
    print(NO_ANSWER if ans is None else ans)


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/**
 * 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-06 00:37
 * update_at: 2026-10-06 00:37
 */
// main.cpp：嗅探器——找编号最小的 a-b 必经点（删点 + DFS 连通性判定）。
#include <iostream>

typedef long long ll;

int n;                   // 服务器数目
bool conn[105][105];     // conn[i][j] 表示 i、j 之间有双向连接（n<=100 用邻接矩阵）
bool vis[105];           // DFS 的已访问标记

// 从 cur 出发找 dst，跳过点 ban（预置为"已删"），能到返回 true
bool dfs(int cur, int dst, int ban) {
    if (cur == dst) return true;
    vis[cur] = true;
    for (int i = 1; i <= n; i++)
        if (conn[cur][i] && i != ban && !vis[i] && dfs(i, dst, ban)) return true;
    return false;
}

int main() {
    std::cin >> n;
    int i, j;
    while (std::cin >> i >> j) {
        if (i == 0 && j == 0) break; // 0 0 标志拓扑描述结束
        conn[i][j] = conn[j][i] = true;
    }
    int a, b; // 两个信息中心
    std::cin >> a >> b;

    // v 是必经点 <=> 删掉 v 后 a 到不了 b；排除 a、b 自身（它们不是"中间"服务器）
    for (int v = 1; v <= n; v++) {
        if (v == a || v == b) continue;
        for (int k = 1; k <= n; k++) vis[k] = false;
        if (!dfs(a, b, v)) {
            std::cout << v << std::endl;
            return 0;
        }
    }
    std::cout << "No solution" << std::endl;
    return 0;
}

「一本通 3.6 练习 2」嗅探器

目录

题目描述

思路

参考代码