服务失效判断
标题：服务失效判断 | 时间限制：1秒 | 内存限制：32768K | 语言限制：不限
某系统中有众多服务，每个服务用字符串（只包含字母和数字，长度<=10）唯一标识，服务间可能有依赖关系，如A依赖B，则当B故障时导致A也故障。
依赖具有传递性，如A依赖B，B依赖C，当C故障时导致B故障，也导致A故障。
给出所有依赖关系，以及当前已知故障服务，要求输出所有正常服务。
input_lst1 = input().split(',')
d = dict()
g = dict()
time = dict()
now = 0
for ele in input_lst1:
s1, s2 = ele.split('-')
time[s1] = now
now += 1
time[s2] = now
now += 1
if s1 not in d:
d[s1] = 0
d[s1] += 1
if s2 not in d:
d[s2] = 0
if s2 not in g:
g[s2] = list()
g[s2].append(s1)
input_lst2 = input().split(',')
h = dict()
for ele in input_lst2:
h[ele] = 1
q = list()
num1, num2 = 0, -1
for ele in d:
if d[ele] == 0 and ele not in h:
q.append(ele)
num2 += 1
answer = list()
while num1 <= num2:
now = q[num1]
num1 += 1
answer.append([time[now], now])
for ele in g[now]:
d[now] -= 1
if d[now] == 0 and ele not in h:
q.append(ele)
num2 += 1
answer.sort()
dn = list()
for ele in answer:
dn.append(ele[1])
if dn:
print(','.join(dn))
else:
print(',')
from collections import defaultdict
def is_normal(matrix,errors):
temp = errors
for error in errors:
if error not in matrix.keys():
continue
else:
for value in matrix[error]:
if value not in temp:
temp.append(value)
if errors != temp:
is_normal(matrix,temp)
else:
return errors
while True:
try:
relation,errors = input().split(","), input().split(",")
matrix,items = defaultdict(list),list()
for r in relation:
a,b = r.split("-")
for x in [a,b]:
if x not in items:
items.append(x)
matrix[b].append(a)
ret = is_normal(matrix,errors)
normal = [item for item in items if item not in ret]
print(",".join(normal) if normal else ",")
except:
break
查看1道真题和解析