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

题目描述

小红需要部署 n 个名称互不相同的服务。一个服务只有在它依赖的所有前驱服务均已部署后才能部署。
若依赖图中存在环，则无法完成部署。否则，请输出字典序最小的合法部署顺序：每一步若有多个当前可部署的服务，应优先选择名称字典序最小者。

输入输出

输入描述
第一行输入整数 n 。
接下来 n 行，每行先输入服务名和依赖数量 m_i ，随后输入该服务依赖的 m_i 个前驱服务名。
保证 1 ≤ n ≤ 1000 ， 0 ≤ m_i < n ，所有依赖服务均在输入中出现；服务名由小写字母和数字组成，长度不超过 100 ；同一行依赖不重复且服务不依赖自身；依赖总数不超过 2 × 10^5 。
输出描述
若依赖图无环，输出一行字典序最小的合法部署顺序，名称间以一个空格分隔；否则输出 `Can not deploy`。

样例共 2 组

样例 1 · 三个服务形成环。
输入
3
aa 1 bb
bb 1 cc
cc 1 aa
输出
Can not deploy
样例 2 · 每一步从当前零入度服务中选择字典序最小者。
输入
5
payment 2 auth order
order 1 user
auth 1 database
user 0
database 0
输出
database auth user order payment

算法解析依据充分

考点：图

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

题目画像

  • 数据规模：n ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：图

本题切入点

拓扑排序 + 字典序最小：用最小堆维护当前入度为 0 的服务，每次取字典序最小者弹出并松弛后继；若最终输出不足 n 个说明有环，输出 Can not deploy。

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。

样例解读

样例 1：输入 3 / aa 1 bb / bb 1 cc / cc 1 aa → 输出 Can not deploy

三个服务形成环。

样例 2：输入 5 / payment 2 auth order / order 1 user / auth 1 database / user 0 / database 0 → 输出 database auth user order payment

每一步从当前零入度服务中选择字典序最小者。

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

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

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