110. 华为OD-服务失效判断(200分)

难度 5
  • 标签:
  • 华为OD真题200分题型
题目描述
题解
题库

华为OD-服务失效判断(200分)

题目内容

某系统中有众多服务,每个服务用字符串(只包含字母和数字,长度10\leq10)唯一标识,服务间可能有依赖关系,如 AA 依赖 BB ,则当 BB 故障时导致 AA 也故障。

依赖具有传递性,如 AA 依赖 BBBB 依赖 CC ,当 CC 故障时导致 BB 故障,也导致 AA 故障。

给出所有依赖关系,以及当前已知故障服务,要求输出所有正常服务。

依赖关系:服务 11 -服务 22 表示“服务 11 ”依赖“服务 22

不必考虑输入异常,用例保证:依赖关系列表、故障列表非空,且依赖关系数,故障服务数都不会超过30003000 ,服务标识格式正常。

输入描述

半角逗号分隔的依赖关系列表(换行)

半角逗号分隔的故障服务列表

输出描述

依赖关系列表中提及的所有服务中可以正常工作的服务列表,用半角逗号分隔,按依赖关系列表中出现的次序排序。

特别的,没有正常节点输出单独一个半角逗号。

样例1

输入

a1-a2,a5-a6,a2-a3
a5,a2

输出

a6,a3

说明

a1a1 依赖 a2a2a2a2 依赖 a3a3 ,所以 a2a2 故障,导致 a1a1 不可用,但不影响 a3a3a5a5 故障不影响 a6a6

所以可用的是 a3a3a6a6 ,在依赖关系列表中 a6a6 先出现,所以输出:a6,a3a6,a3

样例2

输入

a1-a2
a2

输出

,

说明

a1a1 依赖 a2a2a2a2 故障导致 a1a1 也故障,没有正常节点,输出一个逗号。