Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is 2039 on LeetCode. The network is idle, and the difficulty is medium.

Tag: “BFS”

You are given a computer network with NNN servers numbered from 000 to N − 1n-1n −1. Edges [I]=[UI,vi]edges[I]=[u_i, v_i]edges[I]=[UI,vi] Indicates that there is an information line between uiU_iUI and VIv_ivi. They can transmit any number of messages between them in a second. And I’m going to give you an integer array of length NNN starting at 000 patience.

The topic guarantees that all servers are interconnected, that is, a message can be sent from any server to any other server directly or indirectly through these message lines.

The server numbered 000 is the primary server and the other servers are data servers. Each data server sends a message to the master server and waits for a response. Information travels from server to server on an optimal route, meaning that each message gets to the master server in the least amount of time. The master server processes all incoming messages and immediately sends a reply in the opposite direction of where each message came from.

At the beginning of 000 seconds, all data servers send the information they need to process. At the beginning of each second, starting at 111 seconds, each data server checks whether it has received a reply from the master server (including a reply from the new message) :

  • If no reply is received, the server periodically resends the message. Data server III resend a message every [I]patience[I]patience[I], that is, Data server III will send a message to the master server again seconds after the last message was sent to the master server patience[I]patience[I].
  • Otherwise, the data server will not resend the message.

When no information is transmitted over the line or reaches a server, the computer network becomes idle.

Return to the earliest number of seconds in which the computer network became idle.

Example 1:

Edges: input: edges = [[0,1],[1,2]], Patience = [0,2,1] Output: 8 Interpretation: 0 seconds At the beginning, - Data server 1 emits information to the primary server (denoted by 1A). - Data server 2 sends information (denoted by 2A) to the master server. At 1 second, - message 1A arrives at the master server, which immediately processes message 1A and sends a reply message for message 1A. - Data server 1 has not received any reply yet. One second had passed since the last message was sent (1 < patience[1] = 2), so the message would not be repeated. - Data server 2 has not received any reply yet. A second had passed since the last message was sent (1 == patience[2] = 1), so it sent another message (denoted by 2B). After 2 seconds, - reply message 1A reaches server 1, and server 1 does not resend the message. - Message 2A reaches the master server, which immediately processes message 2A and sends a reply message to message 2A. - Server 2 resends a message (expressed in 2C). . After 4 seconds, - reply message 2A reaches server 2, and server 2 does not resend the message. . At 7 seconds, the reply message 2D reaches server 2. From the 8th second onwards, no more information is transferred between the servers and no more information arrives at the server. So 8 seconds is the earliest moment when the network becomes idle.Copy the code

Example 2:

Edges input: edges = [[0,1],[0,2], patience = [0,10,10] output: 3 interpretation: data servers 1 and 2 received a reply at the beginning of second 2. From the third second, the network becomes idle.Copy the code

Tip:


  • n = = p a t i e n c e . l e n g t h n == patience.length

  • 2 < = n < = 1 0 5 2 <= n <= 10^5

  • p a t i e n c e [ 0 ] = = 0 patience[0] == 0
  • For 1 < = I < n1 < = I < n1 < = I < n, 1 < = patience [I] < = 1051 < = patience [I] 51 < < = 10 ^ = patience [I] < = 105

  • 1 < = e d g e s . l e n g t h < = min ⁡ ( 105 . n ∗ ( n – 1 ) / 2 ) 1 <= edges.length <= \min(105, n * (n – 1) / 2)

  • e d g e s [ i ] . l e n g t h = = 2 edges[i].length == 2

  • 0 < = u i . v i < n 0 <= ui, vi < n

  • u i ! = v i ui ! = vi
  • There will be no heavy edges.
  • Each server is directly or indirectly connected to another server.

Figure + BFS was built

According to the title, this is an undirected connected graph with edge weight of 111. We can preprocess the distdistdist array by “adjacency list construction diagram + BFS”. Dist [I]dist[I] refers to the shortest distance from node III to the point no. 000.

The time consumed by a data server III to send messages to the master server is the shortest path dist[I]dist[I]dist[I] between the two nodes, and the time required from sending messages to receiving replies is di=2∗dist[I]di=2 * dist[I]di=2∗dist[I].

Each data server also has a restart of t=patience[I] T =patience[I]t=patience[I] and will stop only after receiving the first response from the master service.

Therefore, if di<=tdi <=tdi <=t, then the data server will not restart, and the node activity stops at dididi. When di> TDI > TDI > T, the data server will restart, and the sending time of the last data packet is (di−1)/t∗t(DI-1)/t * T (DI −1)/t∗t. All activities on this node will stop only when the last data packet receives a reply. Stop time point for (di – 1)/t ∗ t + di (di – 1)/t * t + di (di – 1)/t ∗ t + di. The maximum stop time for all nodes is the answer.

Some details: As usual, we use static optimization to avoid each sample being a new large array. With static optimization, you can even get a stable result of 100100100% 🤣

Code:

class Solution {
    static int N = 100010, M = N * 2, INF = 0x3f3f3f3f;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    static int[] dist = new int[N];
    int idx;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Arrays.fill(he, -1);
        Arrays.fill(dist, INF);
        int n = patience.length;
        for (int[] e : edges) {
            add(e[0], e[1]);
            add(e[1], e[0]);
        }
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0);
        dist[0] = 0;
        while(! d.isEmpty()) {int t = d.pollFirst();
            for (inti = he[t]; i ! = -1; i = ne[i]) {
                int j = e[i];
                if(dist[j] ! = INF)continue;
                dist[j] = dist[t] + 1; d.addLast(j); }}int ans = 0;
        for (int i = 1; i < n; i++) {
            int di = dist[i] * 2, t = patience[i];
            int cur = di <= t ? di : (di - 1) / t * t + di;
            if (cur > ans) ans = cur;
        }
        return ans + 1; }}Copy the code
  • Time complexity: O(n+m)O(n +m)O(n +m)
  • Space complexity: O(n+m)O(n +m)O(n +m)

The last

This is the No.2039 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.