The Time When the Network Becomes Idle — LeetCode 2039 Python Solution

The problem

There is a network of n servers, labeled from 0 to n - 1. You are given a 2D integer array edges, where edges[i] = [ui, vi] indicates there is a message channel between servers ui and vi, and they can pass any number of messages to each other directly in one second.

Example

Input

edges = [[0,1],[1,2]], patience = [0,2,1]

Output

8

Explanation

At (the beginning of) second 0,

Python solution

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        g = defaultdict(list)
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        q = deque([0])
        vis = {0}
        ans = d = 0
        while q:
            d += 1
            t = d * 2
            for _ in range(len(q)):
                u = q.popleft()
                for v in g[u]:
                    if v not in vis:
                        vis.add(v)
                        q.append(v)
                        ans = max(ans, (t - 1) // patience[v] * patience[v] + t + 1)
        return ans

Complexity

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 2039. The Time When the Network Becomes Idle is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Related problems