Java&C++题解与拓展——leetcode2039.网络空闲的时刻【链式前向星存图学习与使用】

题目要求思路：BFS

Java

链式前向星 C++ 总结

由题目可知，服务器实际构成一张无向图，所以想到BFS方式预处理出一个distance数组，表示各节点到0号点的最短距离。
各节点与0号距离为 d i s t dist dist，则发送消息立刻收到回复的时间至少为 t i m e = d i s t ∗ 2 time=dist*2 time=dist∗2，而每个节点的耐心为 T T T，则

当 t i m e ≤ T timele T time≤T时，该节点收到回复的时间为time；当 t i m e > T time>T time>T时，节点需未在耐心限度内收到回复开始重发消息，其最多发送 ⌊ t i m e T ⌋ lfloor frac{time}{T} rfloor ⌊Ttime​⌋次消息，则其收到回复的时间即为 ⌊ t i m e T ⌋ × T + t i m e lfloor frac{time}{T} rfloor times T+time ⌊Ttime​⌋×T+time。

【另：使用static是因为leetcode的判定机制，可避免每个样例都new新的大数组（题目限制为 1 0 5 10^5 105），可优化其判定的运行效率】

采用链式前向星方式建图。

class Solution {
    static int N = 100001, M = N * 2, INF = 0x3f3f3f3f;
    static int[] head = new int[N], edge = new int[M], next = new int[M];
    static int[] dist = new int[N]; //各数据服务器到主服务器距离
    int idx;

    //数组替代邻接表存图
    void add(int a, int b) {
        edge[idx] = b;
        next[idx] = head[a];
        head[a] = idx++;
    }

    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Arrays.fill(head, -1);
        Arrays.fill(dist, INF);
        int plen = patience.length;

        for(int[] e : edges) {
            add(e[0], e[1]);
            add(e[1], e[0]);
        }

        Deque que = new ArrayDeque<>(); //队列，先进先出
        que.addLast(0);
        dist[0] = 0;
        while(!que.isEmpty()) {
            int t = que.pollFirst();
            for(int i = head[t]; i != -1; i = next[i]) {
                int j = edge[i];
                if(dist[j] != INF)
                    continue;
                dist[j] = dist[t] + 1;
                que.addLast(j);
            }
        }

        int res = 0;
        for(int i = 1; i < plen; i++) {
            int time = dist[i] * 2, T = patience[i];
            //最后一个服务器收到回复
            int cur = time <= T ? time : (time - 1) / T * T + time;
            if(cur > res)
                res = cur;
        }
        return res + 1;
    }
}

时间复杂度： O ( m + n ) O(m + n) O(m+n)， m m m为边数， n n n为节点数空间复杂度： O ( m + n ) O(m + n) O(m+n) 链式前向星

学习参考链接引入next表和head表，前者给每个边编号，后者存储每个点对应的第一条边。 C++

思路同上，建图方式更易于理解。

class Solution {
public:
    int networkBecomesIdle(vector>& edges, vector& patience) {
        int plen = patience.size();     
        vector> adj(plen);
        vector visit(plen, false);

        for (auto & e : edges) {
            adj[e[0]].emplace_back(e[1]);
            adj[e[1]].emplace_back(e[0]);
        }

        queue que;
        que.emplace(0);
        visit[0] = true;
        int dist = 1;
        int res = 0;
        while (!que.empty()) {
            int qs = que.size();
            for (int i = 0; i < qs; ++i) {
                int t = que.front();
                que.pop();
                for (auto & v : adj[t]) {
                    if (visit[v])
                        continue;

                    que.emplace(v);
                    int T = patience[v], time = dist * 2;
                    int cur = time <= T ? time : (time - 1) / T * T + time;
                    res = max(res, cur);
                    visit[v] = true;
                }
            }
            dist++;
        }
        return res + 1;
    }
};

时间复杂度： O ( m + n ) O(m + n) O(m+n)空间复杂度： O ( m + n ) O(m + n) O(m+n) 总结

题目关键在于建图和计算最后一个服务器收到回复的时间点。
建图方式需掌握邻接表存图的方法，以及文中提到的用数组替代链表的方法，后续“图”相关题即可套用。
同时两种语言编写时，要注意二者实现队列时使用的类与方法（ArrayDeque和queue）存在一定差异，需对底层逻辑有一定了解。