【每日一题Day39】细分图中的可到达节点 | 图论

细分图中的可到达节点【LC882】

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。

图用由边组成的二维数组 edges 表示，其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边，cnti 是将边 细分 后的新节点总数。注意，cnti == 0 表示边不可细分。

要 细分 边 [ui, vi] ，需要将其替换为 (cnti + 1) 条新边，和 cnti 个新节点。新节点为 x1, x2, …, xcnti ，新边为 [ui, x1], [x1, x2], [x2, x3], …, [xcnti+1, xcnti], [xcnti, vi] 。

现在得到一个 新的细分图 ，请你计算从节点 0 出发，可以到达多少个节点？如果节点间距离是 maxMoves 或更少，则视为 可以到达 。

给你原始图和 maxMoves ，返回 新的细分图中从节点 0 出发 *可到达的节点数* 。

You are given an undirected graph (the “original graph”) with n nodes labeled from 0 to n - 1. You decide to subdivide each edge in the graph into a chain of nodes, with the number of new nodes varying between each edge.

The graph is given as a 2D array of edges where edges[i] = [ui, vi, cnti] indicates that there is an edge between nodes ui and vi in the original graph, and cnti is the total number of new nodes that you will subdivide the edge into. Note that cnti == 0 means you will not subdivide the edge.

To subdivide the edge [ui, vi], replace it with (cnti + 1) new edges and cnti new nodes. The new nodes are x1, x2, …, xcnti, and the new edges are [ui, x1], [x1, x2], [x2, x3], …, [xcnti-1, xcnti], [xcnti, vi].

In this new graph, you want to know how many nodes are reachable from the node 0, where a node is reachable if the distance is maxMoves or less.

Given the original graph and maxMoves, return the number of nodes that are reachable from node 0 in the new graph.

今天的官题写的还不错
[全市静默的第二天 感觉再关几天就学不动了 😐]

• 思路

  • 首先考虑简单情况：当图中只存在原始节点而不存在细分节点时，此题可以用 Dijkstra 算法解决：将输入的 edgess 转换成邻接表 adList，维护一个小顶堆 pq 可以依次计算出图中的起点到各个点最短路径，从而计算出可到达节点。

    • pq 中的元素为节点编号以及起点到该节点的路径长度，并以路径长度为比较元素。每次取出未访问过的节点中的路径最短的节点，并访问其邻接点，若路径长度仍小于等于 maxMoves 且未访问过，可将其放入 pq，直至 pq 为空或 pq最短路径大于maxMoves。

  • 再考虑当每条边上都加入细分节点后，需要考虑细分节点是否可达。

    • 用一个哈希表 used 记录各条边上的细分节点的可达情况，键为二元点对 (u,v)表示从点 u到点 v的边，值为这条边上的可达细分节点数。注意在计算细分节点时，是考虑单向的情况，即会分别计算 used[(u,v)]和 used[(v,u)]，并且这两个值不一定相等。计算 used 时，是要在访问路径最短的节点u 的邻接节点 v 时计算。
    • 如果邻接节点的路径长度小于等于 maxMoves，说明这条边上的细分节点都可达，否则只有一部分可达，且这部分细分节点是靠近节点 u 的。
    • 计算总的可达节点时，需要加上细分节点的部分。但每条边上的细分节点可能会被计算过两次，即 used[(u,v) ]和 used[(v,u)]，他们分别是是靠近 u开始计算的和靠近 v开始计算的，因此需要对这两部分进行去重。

• 实现

  class Solution {
      public int reachableNodes(int[][] edges, int maxMoves, int n) {
          // 初始化邻接表
          List<int[]>[] adList = new List[n];
          for (int i = 0; i < n; i++) {
              adList[i] = new ArrayList<int[]>();
          }
          for (int[] edge : edges) {
              int u = edge[0], v = edge[1], nodes = edge[2];
              adList[u].add(new int[]{v, nodes});
              adList[v].add(new int[]{u, nodes});
          }
          Map<Integer, Integer> used = new HashMap<Integer, Integer>();// 细分情况下、新节点编号能够到达的新结点数【可能为负数】
          Set<Integer> visited = new HashSet<Integer>();
          int reachableNodes = 0;
          PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);// 存储起点至节点的最短路径 a[0]为路径 从小到大存储
          pq.offer(new int[]{0, 0});
  
          while (!pq.isEmpty() && pq.peek()[0] <= maxMoves) {
              int[] pair = pq.poll();
              int step = pair[0], u = pair[1];// u为当前节点 step为节点0至u的最短距离
              if (!visited.add(u)) {// 如果u已经被访问过 那么跳过该节点 避免重复计算
                  continue;
              }
              reachableNodes++;// 记录能够到达的原节点数量
              for (int[] next : adList[u]) {// 存入下一个可以访问的节点
                  int v = next[0], nodes = next[1];
                  if (nodes + step + 1 <= maxMoves && !visited.contains(v)) {
                      pq.offer(new int[]{nodes + step + 1, v});// 能够访问 入队
                  }
                  used.put(encode(u, v, n), Math.min(nodes, maxMoves - step));
              }
          }
          // 计算能够到达的新节点的数量
          for (int[] edge : edges) {
              int u = edge[0], v = edge[1], nodes = edge[2];
              reachableNodes += Math.min(nodes, used.getOrDefault(encode(u, v, n), 0) + used.getOrDefault(encode(v, u, n), 0));
          }
          return reachableNodes;
      }
      // 生成细分图中的节点编号
      public int encode(int u, int v, int n) {
          return u * n + v;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45

  • 复杂度

    • 时间复杂度：O(E×logV)，V 为节点数，即 n，E为输入edges 的长度。邻接表 adList的时间复杂度为 O(E)，Dijkstra 算法的时间复杂度为 O(E×log⁡V)。总的时间复杂度为 O(E×log⁡V)。
    • 空间复杂度：O(V+E)，邻接表 adList 的空间复杂度为 O(E)，pq 的空间复杂度为 O(E)，visited 的空间复杂度为 O(V)，used 的空间复杂度为 O(E)，总的空间复杂度为 O(V+E)。

作者：力扣官方题解
链接：https://leetcode.cn/problems/reachable-nodes-in-subdivided-graph/solutions/1990614/xi-fen-tu-zhong-de-ke-dao-da-jie-dian-by-u8m1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。