)
找孤立水站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−10n≤10000sources整型数组数组元素为源头水站编号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 非孤立站所以系统无孤立站。解题思路本题本质上是有向图的可达性搜索从所有源头站出发通过管道单向/双向能到达的水站都是有供水的反之无法到达的水站即为孤立站。算法步骤建立邻接表根据管道类型建图单向管道只加一条有向边双向管道加两条有向边。BFS 多源遍历所有源头站同时入队标记为已访问已有供水。沿水流方向扩展从已访问水站出发通过邻接表扩展到相邻水站直到队列为空。最终 visited 数组标记了所有能获得供水的水站。收集结果遍历 0 到 n-1未被访问的水站编号即为孤立站按从小到大顺序收集。复杂度分析时间复杂度: O(n m)其中 m 为管道数量每个节点和边最多访问一次。空间复杂度: O(n m)邻接表和访问数
