【BFS】2023Q1A-微服务的集成测试
题目描述与示例
题目描述
现在有 n 个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖），其次服务自身启动加载会消耗一些时间。
给你一个 nxn 的二维矩阵 useTime，其中 useTime[i][i] = 10 表示服务 i 自身启动加载需要消耗 10s，useTime[i][j] = 1 表示服务 i 启动依赖服务 j 启动完成，useTime[i][k] = 0，表示服务 i 启动不依赖服务 k。存在0 <= i，j，k < n。
服务之间启动没有循环依赖（不会出现环），若想对任意一个服务 i 进行集成测试（服务 i 自身也需要加载），求最少需要等待多少时间。
输入描述
第一行输入服务总量 n，之后的 n 行表示服务启动的依赖关系以及自身启动加载耗时 最后输入 k 表示计算需要等待多少时间后可以对服务 k 进行集成测试 其中 1 <= k <= n，1<=n<=100
输出描述
最少需要等待多少时间(s)后可以对服务 k 进行集成测试
示例一
输入
3
5 0 0
1 5 0
0 1 5
3
输出
15
说明
服务3 启动依赖服务2，服务 2 启动依赖服务 1，由于服务 1,2,3 自身加载需要消耗 5s，所以 5+5+5=15，需等待 15s 后可以对服务 3 进行集成测试
示例二
输入
3
5 0 0
1 10 1
1 0 11
2
输出
26
说明
服务 2 启动依赖服务 1 和服务 3，服务 3 启动需要依赖服务 1，服务 1,2,3 自身加载需要消耗 5s，10s，11s，所以 5+10+11=26，需等待 26s 后可以对服务 2 进行集成测试
示例三
输入
4
2 0 0 0
0 3 0 0
1 1 4 0
1 1 1 5
4
输出
12
说明
服务 3 启动依赖服务 1 和服务 2，服务 4 启动需要依赖服务 1,2,3，服务 1,2,3,4 自身加载需要消耗 2s，3s，4s，5s，所以 3+4+5=12s（因为服务 1 和服务 2 可以同时启动），需等待 12s 后可以对服务 4 进行集成测试
示例四
输入
5
1 0 0 0 0
0 2 0 0 0
1 1 3 0 0
1 1 0 4 0
0 0 1 1 5
5
输出
11
说明
服务 3 启动依赖服务 1 和服务 2，服务 4 启动需要依赖服务 1,2，服务 5 启动需要依赖服务 3,4，服务 1,2,3,4,5 自身加载需要消耗 1s，2s，3s，4s，5s，所以 2+4+5=11s（因为服务 1 和服务 2 可以同时启动，服务 3 和服务 4 可以同时启动），需等待 11s 后可以对服务 5 进行集成测试
解题思路
本题在常规的拓扑排序问题上加多了启动时间这一个限制条件，属于变形题。
代码
# 题目：2023Q1A-微服务的集成测试
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：拓扑排序BFS
# 代码看不懂的地方，请直接在群上提问
from collections import deque, defaultdict
# 输入节点数n
n = int(input())
# 输入关联矩阵
isConnected = list()
for _ in range(n):
isConnected.append(list(map(int, input().split())))
# 输入最后要查询的节点k，题目的索引是从1开始的，而我们储存数据的索引是从0开始的
# 故此处应该进行一个-1操作。譬如，服务4实际上是代码中的节点3。
k = int(input())-1
# 初始化入度数组，长度为n
inDegreeList = [0] * n
# 将关联矩阵isConnected转为熟悉的、方便操作的邻接表neighbor_table
neighbor_table = defaultdict(list)
for i in range(n):
for j in range(n):
# i依赖于j，要先运行了j才能运行i。注意此处i不能等于j
if isConnected[i][j] == 1 and i != j:
# 记录j的下一个邻接点包含i
neighbor_table[j].append(i)
# 同时i的入度+1
inDegreeList[i] += 1
# 构建数组loadTimeList，储存每一个节点加载自身所需要的时间
loadTimeList = [isConnected[i][i] for i in range(n)]
# 初始化队列，用于维护BFS过程，起始搜索点为入度为0的节点
q = deque([i for i in range(n) if inDegreeList[i] == 0])
# 构建长度为n的时间数组totalTime，totalTime[i]表示第i个节点启动需要花费的总时间
totalTime = [0] * n
# 进行BFS
while len(q) > 0:
# 弹出当前队头节点cur，说明cur是可以启动的
cur = q.popleft()
# cur节点启动的总时间，要加上其加载自身所需要的时间loadTimeList[cur]
totalTime[cur] += loadTimeList[cur]
# 如果发现弹出的节点cur就是所需要寻找的节点k，可以直接退出BFS循环，完成搜索
# 注意这个判断条件可以不加
if cur == k:
break
# 遍历所有cur的下一个运行节点nxt
for nxt in neighbor_table[cur]:
# nxt的入度减少1
inDegreeList[nxt] -= 1
# nxt的启动总时间，在未考虑nxt自身加载时间时，依赖于所有前置节点的启动时间，
# 若出现前置节点totalTime[cur]启动总时间 > nxt启动总时间totalTime[nxt]
# 则totalTime[nxt]需要以前置节点启动总时间为准
totalTime[nxt] = max(totalTime[nxt], totalTime[cur])
# 如果nxt的入度降为0，则可以加入队列中
if inDegreeList[nxt] == 0:
q.append(nxt)
# 输出totalTime[k]即为答案
print(totalTime[k])
时空复杂度
时间复杂度：O(N^2)。需要遍历整个isConnected关联矩阵。
空间复杂度：O(N^2)。邻接表neighbor_table所占空间最大为O(N^2)，其他变量所占空间最大为O(N)
，故总的空间复杂度为O(N^2)。
华为OD算法冲刺训练
-
华为OD算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
-
30+天陪伴式学习，20+直播课时，300+动画图解视频，200+LeetCode经典题，100+华为OD真题，还有简历修改与模拟面试将为你解锁
-
可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)
-
绿色聊天软件戳 sheepvipvip了解更多
