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

本文主要是介绍JavaC++题解与拓展——leetcode2039.网络空闲的时刻【链式前向星存图学习与使用】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

每日一题做题记录，参考官方和三叶的题解

题目要求

在这里插入图片描述

思路：BFS

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

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

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

Java

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

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<Integer> 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)$ ， $m$ 为边数， $n$ 为节点数
空间复杂度： $O (m + n)$

链式前向星

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

C++

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

class Solution {
public:int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {int plen = patience.size();     vector<vector<int>> adj(plen);vector<bool> visit(plen, false);for (auto & e : edges) {adj[e[0]].emplace_back(e[1]);adj[e[1]].emplace_back(e[0]);}queue<int> 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;}
};