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

Difficulty
Medium
Tags
图
BFS
URL
https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/
Star
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。
有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。
同时给你两个节点 node1 和 node2 。
请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。
注意 edges 可能包含环。
示例 1：
notion imagenotion image
输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。
示例 2：
输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。
提示：
  • n == edges.length
  • 2 <= n <= 105
  • 1 <= edges[i] < n
  • edges[i] != i
  • 0 <= node1, node2 < n
通过次数4,007提交次数16,069

法 1 BFS

思路
整体思路是 先 计算好 node1 节点到所有节点的距离， 再计算好所有节点到 node2的距离，然后遍历所有节点，逐次更新答案。
题解
class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        dist_1 = self.helper(edges, node1)
        dist_2 = self.helper(edges, node2)

        ans = (-1, 10**9)       # (节点编号，对应距离的较大值)
        for node in dist_1:
            if node in dist_2:
                dist = max(dist_1[node], dist_2[node])  # 更新结果
                if dist < ans[1] or (dist == ans[1] and node < ans[0]):
                    ans = (node, dist)
        
        return ans[0]


    
    def helper(self, edges, node):
        queue = deque()
        queue.append(node)

        dist = {}
        dist[node] = 0
        step = 0
        while queue:
            step += 1
            size = len(queue)
            while size:
                cur_node = queue.popleft()
                size -= 1
                
                nxt_node = edges[cur_node]
                if nxt_node in dist or nxt_node == -1:
                    continue
                
                dist[nxt_node] = step
                queue.append(nxt_node)

        return dist