2026 华为OD机试真题9月13日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

某公司机房部署了编号为 0∼n−1 的 n 台路由器，用于组成公司网络。

网络工程师通过网桥桥接路由器，将路由器两两连接。网络连通性具备传递性：如果 A 和 B 连通，B 与 C 连通，那么 A 与 C 也可通过 B 进行连通。

现在网络管理员需要进行连通性测试：指定测试的一台路由器，给出有多少台路由器与它连通（不包含自身）。

2026 华为OD机试真题9月13日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

参数 n（1≤n≤10000）为一个整数，表示路由器的数量。

参数 links 为一个二维整数数组，每个元素 [u,v]（0≤u,v≤n−1）表示编号 u 与编号 v 的两台路由器连通，如 [1,2] 表示 1 号与 2 号路由器连通。

参数 target（0≤target≤n−1）为一个整数，表示需要测量的指定路由器编号。

为了便于在线判题，第一行输入路由器数量 n，第二行输入 JSON 风格的连接关系数组 links，第三行输入目标路由器编号 target。

输出描述

输出一个整数，表示与指定路由器连通的路由器数量（不包含其本身）。

示例1

输入

6
[[0,1],[1,2],[3,4],[4,5]]
0

输出

2

说明

0 与 1 连通，1 与 2 连通，所以与 0 连通的是 1、2，数量为 2。

示例2

输入

7
[[0,3],[3,5],[5,0],[2,6],[1,3]]
5

输出

3

说明

0、3、5 三台路由器两两之间都有连接，1 又与 3 连通，因此 5 号路由器所在的网络为 0、1、3、5，除去自身共 3 台。

2 与 6 自成一组，4 没有任何连接，它们都不与 5 连通。

示例3

输入

4
[]
2

输出

说明

没有任何连接关系，2 号路由器不与其他路由器连通，返回 0。

解题思路

核心思想

本题只需要知道目标路由器最终属于哪个连通分量，以及该连通分量中有多少台路由器，并不需要保存每台路由器的全部邻居。因此可以使用并查集处理所有连接关系。

并查集为每个连通分量维护一个代表节点，并在代表节点处记录分量大小。读取一条连接 [u,v] 时：

1. 分别找到 u 和 v 所在分量的根节点。
2. 如果根节点不同，按分量大小将较小集合合并到较大集合。
3. 更新新根节点对应的分量大小。

所有连接处理完毕后，找到 target 所在分量的根节点。该分量大小包含 target 自身，因此答案为：

componentSize[root(target)] - 1

与邻接表加 BFS 相比，并查集不需要保存 O(m) 规模的邻接表，额外空间只与路由器数量 n 有关。重复连接、自环和环形网络也会被自然处理，不会造成重复计数。

算法步骤

1. 初始化 parent[i] = i，表示每台路由器起初各自属于一个连通分量。
2. 初始化 componentSize[i] = 1。
3. 遍历每条连接，通过路径压缩查找两个端点的根节点。
4. 若两个根节点不同，按分量大小进行合并，并累加新根节点的分量大小。
5. 查找 target 的根节点，返回该分量大小减一。

复杂度分析

设连接数量为 m。

• 时间复杂度：O((n + m) × α(n))，其中 α(n) 为反阿克曼函数，在本题规模下可视为常数。
• 空间复杂度：O(n)，用于并查集的父节点和分量大