华为 · 图 · 算法编程题
华为 图 n ≤ 100 时限 1 秒 / 256 MB

题目描述

人偶师爱丽丝正在整理她复杂的“人偶通信网络”。在这个网络中，每个人偶或部件由一个正整数编号表示。若人偶 u 的运作依赖于部件 v ，则会记录一条依赖关系 (u, v, w) ，其中 w 表示 v 必须达到的最低魔法等级（版本号）。
爱丽丝发现，如果依赖关系中存在循环依赖（即一组人偶构成了环，或者某个人偶直接依赖于自身），整个网络就会陷入瘫痪。若不存在循环依赖，为了确保系统稳定性，对于任何被依赖的部件 v ，其实际采用的版本号应为所有指向 v 的依赖关系中所要求的 w 的最大值。
你需要帮助爱丽丝检查网络的稳定性。如果网络稳定，请按原顺序输出更新版本号后的所有依赖关系。

输入输出

输入描述
输入包含恰好两组测试数据。
对于每组数据：
第一行包含一个正整数 n ( 0 < n < 100 )，表示依赖关系的数量。
接下来的 n 行，每行包含一个形如 `u,v,version` 的字符串（由逗号分隔），表示人偶 u 依赖于部件 v ，且要求的版本号为 version 。
数据范围：
- 编号 u, v 为正整数，且 1 ≤ u, v ≤ 10^9 。
- 版本号 1 ≤ version ≤ 99 。
- 在同一组数据中，同一个依赖序对 (u, v) 最多出现一次。
输出描述
对于每组测试数据：
- 如果存在循环依赖，输出一行 `false`。
- 如果不存在循环依赖，对于每一条输入的依赖关系 `u,v,version`，将 version 更新为所有以 v 为被依赖对象的条目中 version 的最大值，并按输入顺序输出更新后的关系，格式为 `u,v,max_version`。

样例共 1 组

样例 1 · 在第一组样例中： - 人偶 1 依赖 2（版本 23），人偶 4 也依赖 2（版本 25）。因此部件 2 的最大需求版本为 25。 - 人偶 2 依赖 3（版本 34）。因此部件 3 的最大需求版本为 34。 - 网络中不存在环，故按原输入顺序输出更新后的三条记录。 在第二组样例中： - 1 依赖 2，2 依赖 3，3 依赖 1，构成了闭环，故输出 `false`。
输入
3
1,2,23
2,3,34
4,2,25
3
1,2,23
2,3,34
3,1,12
输出
1,2,25
2,3,34
4,2,25
false

算法解析依据充分

考点：图

数据规模 n ≤ 100 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 100
  • 元素值域：u ≤ 1e9，v ≤ 1e9，version ≤ 99（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：图

本题切入点

依赖关系构成有向图：用拓扑排序判环（含自环），无环时对每个被依赖对象 v 取其所有入边的最大版本号，再按输入顺序输出更新后的关系。

把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。

思路框架（图 通法 · 非本题专属）

  1. 建图：邻接表（稀疏）或邻接矩阵（稠密）。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra（非负权）或 Floyd（点数小、多源）。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点：注意是有向图还是无向图，无向图加边记得双向。

复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问，导致重复入队。

对照本题

  • 数据规模 n ≤ 100，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 / 1,2,23 / 2,3,34 / 4,2,25 / 3 / 1,2,23 / 2,3,34 / 3,1,12 → 输出 1,2,25 / 2,3,34 / 4,2,25 / false

在第一组样例中：

  • 人偶 1 依赖 2（版本 23），人偶 4 也依赖 2（版本 25）。因此部件 2 的最大需求版本为 25。
  • 人偶 2 依赖 3（版本 34）。因此部件 3 的最大需求版本为 34。
  • 网络中不存在环，故按原输入顺序输出更新后的三条记录。

在第二组样例中：

  • 1 依赖 2，2 依赖 3，3 依赖 1，构成了闭环，故输出 false。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2026年-华为-04月22号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解