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

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

题目描述

城市供水管道由若干个连接外部的源头水站，以及内部水站、水管组成。 全市共有 n 个水站，编号为 0 至 n−1。 供水网络由若干管道连接，管道分为两类：

• 单向管道 (Type 0)：水流只能从水站 u 流向水站 v。
• 双向管道 (Type 1)：水流可以在水站 u 和 v 之间双向流动。

受战争影响，城市中的一部分供水管道破裂导致部分水站无法获得供水，我们称为孤立站。

假设源头站一定有水（非孤立站），请你根据输入的各个水站的联通情况，输出孤立站的列表，从小到大进行排列。

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

输入描述

n：整型，水站数量，水站编号为 0 至 n−1，0<n≤10000；

sources：整型数组，数组元素为源头水站编号；

pipes：二维数组，数组元素为 [u,v,type]，表示水站连通关系，其中 u,v 为水站编号，type 为连通类型。

• [u,v,0] 表示：单向管道，水可由u流向v，不可由v流向u

• [u,v,1] 表示：双向管道，水可由u流向v，也可由v流向u

输入格式：n,sources,pipes，例如：5,[1],[[1,0,0],[1,2,0]]

输出描述

孤立站列表，类型为整型数组，数组元素为孤立站编号，结果从小到大排列。

输出格式：[站编号1,站编号2,...]，若无孤立站则输出[]。

示例1

输入

5,[1],[[1,0,0],[1,2,0]]

输出

[3,4]

说明

1 号为源头站，从 1 号到 0 号和 2 号都有单向流动，3 号、4 号为孤立站。

示例2

输入

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

输出

[4]

说明

0 号、1 号是源头站，0、1 非孤立站；

0 号向 2 号和 3 号是单向流通，2、3 非孤立站；

4 号向 3 号单向流通，但是无水站向 4 号供水，4 是孤立站。

示例3

输入

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

输出

[]

说明

0 号站到 1 号、2 号为双向流通，1、2 非孤立站；

3 号、4 号到 2 号为双向流通，3、4 非孤立站；

所以系统无孤立站。

解题思路

本题本质上是有向图的可达性搜索：从所有源头站出发，通过管道（单向/双向）能到达的水站都是有供水的，反之无法到达的水站即为孤立站。

算法步骤：

1. 建立邻接表：根据管道类型建图，单向管道只加一条有向边，双向管道加两条有向边。
2. BFS 多源遍历：所有源头站同时入队，标记为已访问（已有供水）。
3. 沿水流方向扩展：从已访问水站出发，通过邻接表扩展到相邻水站，直到队列为空。最终 visited 数组标记了所有能获得供水的水站。
4. 收集结果：遍历 0 到 n-1，未被访问的水站编号即为孤立站，按从小到大顺序收集。

复杂度分析

• 时间复杂度: O(n + m)，其中 m 为管道数量，每个节点和边最多访问一次。
• 空间复杂度: O(n + m)，邻接表和访问数