2039.md

2039. The Time When the Network Becomes Idle

Solution 1 (time O(m+n), space O(m+n))

class Solution(object):
    def networkBecomesIdle(self, edges, patience):
        """
        :type edges: List[List[int]]
        :type patience: List[int]
        :rtype: int
        """
        n = len(patience)
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        vis = [0 for _ in range(n)]
        vis[0] = 1
        q = deque([0])
        ans = 0
        dist = 1
        while q:
            for _ in range(len(q)):
                cur_node = q.popleft()
                for new_node in g[cur_node]:
                    if vis[new_node]:
                        continue
                    vis[new_node] = 1
                    q.append(new_node)
                    ans = max(ans, (dist * 2 - 1) // patience[new_node] * patience[new_node] + dist * 2 + 1)
            dist += 1
        return ans