网络空闲的时刻

难度: Medium

给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [u_i, v_i] 表示服务器 u_i 和 v_i之间有一条信息线路，在一秒内它们之间可以传输任意数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。

题目保证所有服务器都是相通的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。

编号为 0 的服务器是主服务器，其他服务器为数据服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按最优线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理所有新到达的信息并立即按照每条信息来时的路线 反方向 发送回复信息。

在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每一秒最开始时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：

如果还没收到任何回复信息，那么该服务器会周期性重发信息。数据服务器 i 每 patience[i] 秒都会重发一条信息，也就是说，数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒后会重发一条信息给主服务器。
否则，该数据服务器 不会重发 信息。

当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为空闲状态。

请返回计算机网络变为空闲状态的 最早秒数 。

示例 1：

example 1

输入：edges = [[0,1],[1,2]], patience = [0,2,1]
输出：8
解释：
0 秒最开始时，
- 数据服务器 1 给主服务器发出信息（用 1A 表示）。
- 数据服务器 2 给主服务器发出信息（用 2A 表示）。

1 秒时，
- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。

2 秒时，
- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
- 服务器 2 重发一条信息（用 2C 表示）。
...
4 秒时，
- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
...
7 秒时，回复信息 2D 到达服务器 2 。

从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
所以第 8 秒是网络变空闲的最早时刻。

示例 2：

example 2

输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出：3
解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始，网络变空闲。

提示：

n == patience.length
2 <= n <= 10⁵
patience[0] == 0
对于 1 <= i < n ，满足 1 <= patience[i] <= 10⁵
1 <= edges.length <= min(10⁵, n * (n - 1) / 2)
edges[i].length == 2
0 <= u_i, v_i < n
u_i != v_i
不会有重边。
每个服务器都直接或间接与别的服务器相连。

Submission

运行时间: 302 ms

内存: 52.7 MB

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
            
        n = len(patience)
        # 构建图的邻接表表示
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # BFS 计算从主服务器到每个数据服务器的最短距离
        distance = [0] * n  # distance[i] 表示从主服务器到服务器i的最短距离
        visited = [False] * n
        queue = deque([0])
        visited[0] = True
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    distance[neighbor] = distance[node] + 1
                    queue.append(neighbor)

        # 计算变为空闲的时间
        idle_time = 0
        for i in range(1, n):
            round_trip = 2 * distance[i]  # 往返时间
            last_message_time = ((round_trip - 1) // patience[i]) * patience[i] + round_trip  # 最后一次信息的到达时间
            idle_time = max(idle_time, last_message_time)

        return idle_time + 1  # +1 是因为在最后一次信息到达后的下一秒，网络变为空闲

Explain

该题解首先通过构建一个图的邻接表来表示各服务器间的连接关系。利用广度优先搜索（BFS），计算从主服务器（编号为0）到所有其他服务器的最短距离。接着，计算每个数据服务器在不再发送新信息的情况下，最后一条信息的到达时间。这是通过计算每个数据服务器的重发间隔和往返时间来完成的。最终，通过确定所有服务器最后一条信息的到达时间来计算网络何时变为空闲。

时间复杂度: O(V + E)

空间复杂度: O(V + E)

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
            
        n = len(patience)  # 数据服务器的数量
        # 构建图的邻接表表示
        graph = [[] for _ in range(n)]
        for u, v in edges:  # 创建无向边
            graph[u].append(v)
            graph[v].append(u)

        # BFS 计算从主服务器到每个数据服务器的最短距离
        distance = [0] * n  # distance[i] 表示从主服务器到服务器i的最短距离
        visited = [False] * n  # 访问标记数组
        queue = deque([0])  # 使用队列实现BFS
        visited[0] = True  # 标记主服务器已访问
        while queue:  # BFS 主循环
            node = queue.popleft()  # 取出队列首部元素
            for neighbor in graph[node]:  # 遍历当前节点的所有邻居
                if not visited[neighbor]:  # 如果邻居未被访问过
                    visited[neighbor] = True  # 标记为已访问
                    distance[neighbor] = distance[node] + 1  # 更新距离
                    queue.append(neighbor)  # 将邻居节点加入队列

        # 计算变为空闲的时间
        idle_time = 0
        for i in range(1, n):  # 遍历所有数据服务器
            round_trip = 2 * distance[i]  # 往返时间
            last_message_time = ((round_trip - 1) // patience[i]) * patience[i] + round_trip  # 最后一次信息的到达时间
            idle_time = max(idle_time, last_message_time)  # 更新最长等待时间

        return idle_time + 1  # +1 是因为在最后一次信息到达后的下一秒，网络变为空闲

Explore

广度优先搜索（BFS）从起点开始，逐层遍历图中的节点，首先访问起点的直接邻居，再访问直接邻居的邻居，依此类推。由于BFS一层层地扩展，对于任何从起点到达特定节点的路径，当这个节点第一次被访问时，该路径就是从起点到该节点的最短路径。在题解中，使用BFS计算从主服务器（编号0）到其他所有服务器的距离，确保了每次当一个服务器第一次被访问时，记录的路径长度是从主服务器到该服务器的最短距离。

题解中提到所有服务器都是相通的，这意味着从主服务器出发可以到达网络中的任何一个服务器。这个信息的前提简化了算法的实现，因为我们不需要检查连接的完整性或处理无法到达的服务器。在实现BFS时，无需考虑图中是否存在孤立的部分或分支，可以直接假设所有服务器都将在搜索过程中被访问。这减少了算法在处理孤岛或分割网络时可能需要的额外逻辑或错误处理。

题解中计算的`idle_time`是所有数据服务器发出的最后一条信息的到达时间的最大值。通过将这个时间加1，我们得到的`idle_time + 1`代表的是在所有服务器发出的最后一条信息到达后的下一秒，即此刻之后再也没有新的信息被发送或到达。所以，`idle_time + 1`确实表示网络在这一刻完全没有任何数据传输，包括主服务器向数据服务器的回复。这标志着网络空闲的开始时刻。