题面简述
某系统有多个服务,并且服务间可能存在依赖关系。服务之间的依赖是传递性的,即如果一个服务出现故障,它依赖的服务也会受到影响。给定一个依赖关系列表和一个故障服务列表,我们需要找出所有没有故障的服务,并且要求按依赖关系中的出现顺序输出。
题解思路
1. 依赖图的构建
首先,我们可以将服务间的依赖关系看作是一个有向图,其中每个节点代表一个服务,每条边表示一个服务依赖于另一个服务。例如,服务 A 依赖服务 B 这条边表示为 A<-B。因此,我们需要用一个邻接表来表示反向依赖关系(从服务 B 到 A),即每个服务记录哪些其他服务依赖它。
2. 故障服务的影响传播
P3193.服务失效判断(200分)
题目内容
某系统中有众多服务,每个服务用字符串(只包含字母和数字,长度<=10)唯一标识,服务间可能有依赖关系,如 A 依赖 B ,则当 B 故障时导致 A 也故障。
依赖具有传递性,如 A 依赖 B ,B 依赖 C ,当 C 故障时导致 B 故障,也导致 A 故障。
给出所有依赖关系,以及当前已知故障服务,要求输出所有正常服务。
依赖关系:服务 1 -服务 2 表示“服务 1 ”依赖“服务 2 ”