Compute Minimum Integration Test Time for Dependent Microservices with Topological Sort

Problem Description

Given n microservices, each service may depend on other services to start first, and each service also requires a certain amount of time to load itself. The dependency information is provided as an n×n matrix useTime where useTime[i][i] is the self‑load time of service i (in seconds), useTime[i][j]=1 means service i depends on service j, and useTime[i][k]=0 means no dependency. There are no circular dependencies. For a target service k, compute the minimum total time that must elapse before it can be integration‑tested (i.e., all its dependencies have finished loading and it has loaded itself).

Input Format

First line: integer n (1 ≤ n ≤ 100), the number of services.

Next n lines: each line contains n integers describing the matrix useTime.

Last line: integer k (1 ≤ k ≤ n), the index (1‑based) of the service to be tested.

Output Format

Output a single integer – the minimum waiting time (in seconds) required before service k can be integration‑tested.

Examples

Example 1

3
5 0 0
1 5 0
0 1 5
3

Output: 15 Explanation: Service 3 depends on 2, which depends on 1. Each service loads in 5 s, so the total wait is 5 + 5 + 5 = 15 s.

Example 2

3
5 0 0
1 10 1
1 0 11
2

Output: 26 Explanation: Service 2 depends on services 1 and 3, whose load times are 5 s, 10 s, and 11 s respectively, giving 5 + 10 + 11 = 26 s.

Solution Idea

The problem is a variant of topological sorting with an additional load‑time constraint. We treat the dependency matrix as a directed acyclic graph (DAG) where an edge j → i exists if service i depends on j. Using BFS (Kahn's algorithm) we process nodes with zero in‑degree, accumulating the maximum total time required to reach each node. For each node cur we add its own load time loadTimeList[cur] to totalTime[cur]. When propagating to a dependent node nxt, we update totalTime[nxt] to the larger of its current value and totalTime[cur], ensuring that nxt cannot start before all its predecessors have finished. The algorithm stops early if the target node k is dequeued.

Reference Implementation (Python)

# 题目：2023Q1A-微服务的集成测试
# 算法：拓扑排序BFS
from collections import deque, defaultdict

# 输入节点数 n
n = int(input())
# 输入关联矩阵 isConnected
isConnected = []
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

# 输入目标服务 k（1‑based），转为 0‑based
k = int(input()) - 1

# 初始化入度数组
inDegreeList = [0] * n
# 构建邻接表：j -> i 表示 i 依赖 j
neighbor_table = defaultdict(list)
for i in range(n):
    for j in range(n):
        if isConnected[i][j] == 1 and i != j:
            neighbor_table[j].append(i)
            inDegreeList[i] += 1

# 每个节点的自加载时间
loadTimeList = [isConnected[i][i] for i in range(n)]

# 队列初始化，入度为 0 的节点可直接启动
q = deque([i for i in range(n) if inDegreeList[i] == 0])
# totalTime[i] 为启动节点 i 所需的累计时间
totalTime = [0] * n

while q:
    cur = q.popleft()
    totalTime[cur] += loadTimeList[cur]
    if cur == k:
        break
    for nxt in neighbor_table[cur]:
        inDegreeList[nxt] -= 1
        totalTime[nxt] = max(totalTime[nxt], totalTime[cur])
        if inDegreeList[nxt] == 0:
            q.append(nxt)

print(totalTime[k])

Complexity Analysis

Time complexity: O(N²) – we scan the entire isConnected matrix to build the adjacency list.

Space complexity: O(N²) for the adjacency list in the worst case, plus O(N) for auxiliary arrays, resulting in overall O(N²).