给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 n 且下标从 0 开始的整数数组 patience 。
题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。
编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按最优 线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 反方向 发送回复信息。
在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始， 每 一秒最 开始
如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器 i 每 patience[i] 秒都会重发一条信息，也就是说，数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。
否则，该数据服务器 不会重发 信息。
当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。
请返回计算机网络变为 空闲 状态的 最早秒数 。
示例 1：
 / 2)edges[i].length == 20 <= ui, vi < nui != vi不会有重边。
每个服务器都直接或间接与别的服务器相连。
方法一：广度优先搜索 思路
我们可以将整个计算机网络视为一个无向图，服务器为图中的节点。根据图中的边对应的关系 edges 即可求出图中任意节点之间的最短距离。利用广度优先搜索求出节点 0 到其他节点的最短距离，然后依次求出每个节点变为空闲的时间，当所有节点都变为空闲时，整个网络即变空闲状态，因此网络的最早空闲时间即为各个节点中最晚的空闲时间。定义节点的空闲状态定义为该节点不再发送和接收消息。
求各个节点与 0 号服务器的最短路径，直接利用广度优先搜索即可。
设节点 v 与节点 0 之间的最短距离为 dist，则此时当节点 v 接收到主服务器节点 0 的最后一个回复后的下一秒，则节点 v 变为空闲状态。节点 v 发送一个消息经过 dist 秒到达节点 0，节点 0 回复消息又经过 dist 秒到达节点 v，因此节点 v 每发送一次消息后，经过 2 \times \textit{dist 秒才能收到回复。由于节点 v 在未收到节点 0 的回复时，会周期性每 patience}[v] 秒发送一次消息，一旦收到来自节点 0 的回复后就停止发送消息，需要分以下两种情况进行讨论：
当 2 \times \textit{dist} \le \textit{patience}[v] 时，则此时节点 v 还未开始发送第二次消息就已收到回复，因此节点 v 只会发送一次消息，则此时节点 v 变为空闲的时间为 2 \times \textit{dist} + 1。
当 2 \times \textit{dist} > \textit{patience}[v] 时，则此时节点还在等待第一次发送消息的回复时，就会开始再次重发消息，经过计算可以知道在 [1,2 \times \textit{dist}) 时间范围内会最多再次发送 \Big\lfloor\dfrac{2 \times \textit{dist}-1}{\textit{patience}[i]}\Big\rfloor 次消息，最后一次发送消息的时间为 patience}[v] \times \Big\lfloor\dfrac{2 \times \textit{dist}-1}{\textit{patience}[v]}\Big\rfloor，而节点 v 每发送一次消息就会经过 2 \times \textit{dist}[v] 收到回复，因此节点 v 最后一次收到回复的时间为 patience}[v] \times \Big\lfloor\dfrac{2 \times \textit{dist}-1}{\textit{patience}[v]}\Big\rfloor + 2 \times \textit{dist，则此时可知节点 v 变为空闲的时间为 patience}[v] \times \Big\lfloor\dfrac{2 \times \textit{dist}-1}{\textit{patience}[v]}\Big\rfloor + 2 \times \textit{dist} + 1。
当 2 \times \textit{dist} \le \textit{patience}[v] 时，\Big\lfloor\dfrac{2 \times \textit{dist}-1}{\textit{patience}[v]}\Big\rfloor = 0，因此以上两种情况可以进行合并，即节点 v 变为空闲的时间为 patience}[v] \times \Big\lfloor\dfrac{2 \times \textit{dist}-1}{\textit{patience}[v]}\Big\rfloor + 2 \times \textit{dist} + 1。
依次求出每个节点变为空闲的时间，返回最大值即为答案。
代码
[sol1-Python3] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution : def networkBecomesIdle (self, edges: List [List [int ]], patience: List [int ] ) -> int : n = len (patience) g = [[] for _ in range (n)] for u, v in edges: g[u].append(v) g[v].append(u) vis = [False ] * n vis[0 ] = True q = deque([0 ]) ans, dist = 0 , 1 while q: for _ in range (len (q)): u = q.popleft() for v in g[u]: if vis[v]: continue vis[v] = True q.append(v) ans = max (ans, (dist * 2 - 1 ) // patience[v] * patience[v] + dist * 2 + 1 ) dist += 1 return ans
[sol1-C++] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution {public : int networkBecomesIdle (vector<vector<int >>& edges, vector<int >& patience) int n = patience.size (); vector<vector<int >> adj (n); vector<bool > visit (n, false ) ; for (auto & v : edges) { adj[v[0 ]].emplace_back (v[1 ]); adj[v[1 ]].emplace_back (v[0 ]); } queue<int > qu; qu.emplace (0 ); visit[0 ] = true ; int dist = 1 ; int ans = 0 ; while (!qu.empty ()) { int sz = qu.size (); for (int i = 0 ; i < sz; ++i) { int curr = qu.front (); qu.pop (); for (auto & v : adj[curr]) { if (visit[v]) { continue ; } qu.emplace (v); int time = patience[v] * ((2 * dist - 1 ) / patience[v]) + 2 * dist + 1 ; ans = max (ans, time); visit[v] = true ; } } dist++; } return ans; } };
[sol1-Java] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public int networkBecomesIdle (int [][] edges, int [] patience) { int n = patience.length; List<Integer>[] adj = new List [n]; for (int i = 0 ; i < n; ++i) { adj[i] = new ArrayList <Integer>(); } boolean [] visit = new boolean [n]; for (int [] v : edges) { adj[v[0 ]].add(v[1 ]); adj[v[1 ]].add(v[0 ]); } Queue<Integer> queue = new ArrayDeque <Integer>(); queue.offer(0 ); visit[0 ] = true ; int dist = 1 ; int ans = 0 ; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0 ; i < size; i++) { int curr = queue.poll(); for (int v : adj[curr]) { if (visit[v]) { continue ; } queue.offer(v); int time = patience[v] * ((2 * dist - 1 ) / patience[v]) + 2 * dist + 1 ; ans = Math.max(ans, time); visit[v] = true ; } } dist++; } return ans; } }
[sol1-C#] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 public class Solution { public int NetworkBecomesIdle (int [][] edges, int [] patience int n = patience.Length; IList<int >[] adj = new IList<int >[n]; for (int i = 0 ; i < n; ++i) { adj[i] = new List<int >(); } bool [] visit = new bool [n]; foreach (int [] v in edges) { adj[v[0 ]].Add(v[1 ]); adj[v[1 ]].Add(v[0 ]); } Queue<int > queue = new Queue<int >(); queue.Enqueue(0 ); visit[0 ] = true ; int dist = 1 ; int ans = 0 ; while (queue.Count > 0 ) { int size = queue.Count; for (int i = 0 ; i < size; i++) { int curr = queue.Dequeue(); foreach (int v in adj[curr]) { if (visit[v]) { continue ; } queue.Enqueue(v); int time = patience[v] * ((2 * dist - 1 ) / patience[v]) + 2 * dist + 1 ; ans = Math.Max(ans, time); visit[v] = true ; } } dist++; } return ans; } }
[sol1-C] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 static inline int max (int x, int y) { return x > y ? x : y; } int networkBecomesIdle (int ** edges, int edgesSize, int * edgesColSize, int * patience, int patienceSize) { int n = patienceSize; struct ListNode ** adj =struct ListNode **)malloc (sizeof (struct ListNode * ) * n); bool * visit = (bool *)malloc (sizeof (bool ) * n); for (int i = 0 ; i < n; i++) { visit[i] = false ; adj[i] = NULL ; } struct ListNode * node =NULL ; for (int i = 0 ; i < edgesSize; i++) { node = (struct ListNode *)malloc (sizeof (struct ListNode)); node->val = edges[i][0 ]; node->next = adj[edges[i][1 ]]; adj[edges[i][1 ]] = node; node = (struct ListNode *)malloc (sizeof (struct ListNode)); node->val = edges[i][1 ]; node->next = adj[edges[i][0 ]]; adj[edges[i][0 ]] = node; } int * queue = (int *)malloc (sizeof (int ) * n); int head = 0 ; int tail = 0 ; queue [tail++] = 0 ; visit[0 ] = true ; int dist = 1 ; int ans = 0 ; while (head != tail) { int sz = tail - head; for (int i = 0 ; i < sz; ++i) { int curr = queue [head]; head++; for (struct ListNode * node = adj[curr]; node; node = node->next) { int v = node->val; if (visit[v]) { continue ; } queue [tail++] = v; int time = patience[v] * ((2 * dist - 1 ) / patience[v]) + 2 * dist + 1 ; ans = max(ans, time); visit[v] = true ; } } dist++; } free (queue ); free (visit); for (int i = 0 ; i < n; i++) { for (struct ListNode * curr = adj[i]; curr;) { struct ListNode * next = free (curr); curr = next; } } return ans; }
[sol1-Golang] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 func networkBecomesIdle (edges [][]int , patience []int ) int ) { n := len (patience) g := make ([][]int , n) for _, e := range edges { x, y := e[0 ], e[1 ] g[x] = append (g[x], y) g[y] = append (g[y], x) } vis := make ([]bool , n) vis[0 ] = true q := []int {0 } for dist := 1 ; q != nil ; dist++ { tmp := q q = nil for _, x := range tmp { for _, v := range g[x] { if vis[v] { continue } vis[v] = true q = append (q, v) ans = max(ans, (dist*2 -1 )/patience[v]*patience[v]+dist*2 +1 ) } } } return } func max (a, b int ) int { if b > a { return b } return a }
复杂度分析
时间复杂度：O(n + m)，其中 n 为节点的数目，m 为 edges 数组的大小。利用广度优先搜索求每个节点到节点 0 的最短距离的时间复杂度为 O(n + m)，求出每个节点的空闲时间的时间复杂度为 O(n)，因此总的时间复杂度为 O(n + m)。
空间复杂度：O(n + m)，其中 n 为节点的数目，m 为 edges 数组的大小。需要利用 edges 重建图的关系，需要的空间为 O(n + m)，记录每个节点到节点 0 的最短距离需要的空间为 O(n)，因此总的空间复杂度为 O(n + m)。
