点击获取AI摘要

2359. 找到离给定两个节点最近的节点 M

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点至多有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回最小的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

示例 1：

示例1

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。

示例 2：

示例2

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

提示：

n == edges.length
2 <= n <= 10⁵
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n

问题分析

给定一个大小为 $n$ 的有向图，用数组 edges 表示：对于每个节点 $i$ ，如果 edges[i] = j，则存在一条从 $i$ 指向 $j$ 的有向边；如果 edges[i] = -1，则节点 $i$ 没有出边。由于“每个节点最多有一条出边”，图的结构类似若干条链和环的组合。

现有两个起点 node1 和 node2，我们要找到一个目标节点 $x$ ，使得从 node1 到 $x$ 的距离记作 $d_1(x)$ ，从 node2 到 $x$ 的距离记作 $d_2(x)$ 。定义这两个距离的“较大值”为

$\max\bigl(d_1(x),\, d_2(x)\bigr).$

我们需要选择一个节点 $x$ ，使得

$\max\bigl(d_1(x),\, d_2(x)\bigr)$

尽可能小；如果存在多个使得上述值相同的节点，则取编号最小的一个；如果不存在任何节点能同时被 node1 和 node2 到达，则返回 $-1$ 。

由于“每个节点至多一条出边”，从给定起点出发后，只能沿着唯一的一条路径不断前进，不会产生多叉分支。这样，我们可以通过一次“链式遍历”（类似于 BFS，但由于出度为 1，可视作单链 DFS）来计算每个起点到其它所有可达节点的距离。

算法思路

初始化距离数组
对于每个起点 node1 和 node2，分别构造一个长度为 $n$ 的数组 dist1 和 dist2，初始时将所有位置赋值为“无穷大” $\infty$ （可用一个大于 $n$ 的整数代表）。

$\text{对 }i=0\ldots n-1,\quad \mathrm{dist1}[i] = \mathrm{dist2}[i] = \infty.$
计算单源距离
定义一个辅助函数 compute_dist(start, edges) -> dist，其作用为：
- 从 start 开始，令当前节点 $u = start$ ，将 $\mathrm{dist}[u] = 0$ 。
- 然后不断循环：若 edges[u] != -1 且下一个节点 $v = \text{edges}[u]$ 尚未访问过（即 $\mathrm{dist}[v] = \infty$ ），则设置 $\mathrm{dist}[v] = \mathrm{dist}[u] + 1$ ，更新 $u = v$ 继续；否则退出循环（要么碰到 $-1$ ，要么进入已访问节点，形成环，或者到达无出边节点）。
- 返回填充好的 dist 数组。
  由于每个节点只有一条出边，整个过程每个节点最多只会被赋值一次，因此时间复杂度为 $O(n)$ 。
合并结果、寻找答案
- 调用 compute_dist(node1, edges)，得到数组 dist1。
- 调用 compute_dist(node2, edges)，得到数组 dist2。
- 遍历所有节点 $i=0\ldots n-1$ ，如果这两个距离都不是无穷大（即 dist1[i] \neq \infty 且 dist2[i] \neq \infty），则该节点 $i$ 可以同时被两个起点到达，我们计算
  $D(i) \;=\; \max\bigl(\mathrm{dist1}[i],\, \mathrm{dist2}[i]\bigr).$
- 在所有可行的 $i$ 中，选出使得 $D(i)$ 最小的那一个；如果有多个，则取编号最小者。若没有任何可行点，则返回 $-1$ 。

时间复杂度

计算 dist1 的过程：最多沿着一条链走过每个节点一次，时间复杂度是 $O(n)$ 。
同理，计算 dist2 也是 $O(n)$ 。
最后一次遍历所有节点来比较 $\max\bigl(\mathrm{dist1}[i],\mathrm{dist2}[i]\bigr)$ 并更新答案，时间也是 $O(n)$ 。

因此，总的时间复杂度为

$O(n) + O(n) + O(n) \;=\; O(n).$

空间复杂度：我们用了两个长度为 $n$ 的距离数组，加上一些常数级辅助变量，故空间复杂度为 $O(n)$ 。

代码分解

函数 compute_dist(start, edges)
- 输入：起点索引 start，数组 edges（长度为 $n$ ）。
- 输出：长度为 $n$ 的整数数组 dist，其中 dist[i] 表示从 start 到节点 $i$ 的最短距离；如果不可达，则保持 $\infty$ （例如用 $n+1$ 代替）。
- 思路：
  1
  2
  3
  4
  5
  6
  7
  8
  9
  初始化 dist[i] = inf (i = 0..n-1)
  u = start
  d = 0
  while u != -1 且 dist[u] == inf:
  dist[u] = d
  v = edges[u]
  u = v
  d = d + 1
  return dist
主函数 closestMeetingNode(edges, node1, node2)
- 输入：edges 数组，node1，node2。
- 步骤：
  1. 令 $n = \mathrm{len}(edges)$ ，将 $\infty$ 记为 n+1（只要大于可能的最长路径即可）。
  2. 调用 dist1 = compute_dist(node1, edges)；调用 dist2 = compute_dist(node2, edges)。
  3. 令 ans = -1，best = \infty。
  4. 对所有 i 从 $0$ $0$ 到 $n-1$ $n - 1$ ：
    - 若 dist1[i] != \infty 且 dist2[i] != \infty，则计算 dmax = max(dist1[i], dist2[i])。
    - 若 dmax < best，则更新 best = dmax，ans = i；若 dmax == best 且 i < ans，则更新 ans = i（取编号更小）。
  5. 返回 ans。

代码实现

from typing import List

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        # 用 n+1 表示“无穷大”距离，因最大可能距离不会超过 n
        INF = n + 1
        
        def compute_dist(start: int) -> List[int]:
            dist = [INF] * n
            u = start
            d = 0
            # 一路沿着唯一路径走，直到到头或遇已访问节点
            while u != -1 and dist[u] == INF:
                dist[u] = d
                v = edges[u]
                u = v
                d += 1
            return dist
        
        dist1 = compute_dist(node1)
        dist2 = compute_dist(node2)
        
        ans = -1
        best = INF
        for i in range(n):
            if dist1[i] != INF and dist2[i] != INF:
                dmax = max(dist1[i], dist2[i])
                # 如果发现更优的最大距离，更新 ans；相同距离则选更小编号
                if dmax < best or (dmax == best and (ans == -1 or i < ans)):
                    best = dmax
                    ans = i
        
        return ans