LeetCode 题解工作台
找到离给定两个节点最近的节点
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。 有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。 同时给你两个节点 nod…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
我们可以先用 BFS 求出从 和 分别到达每个点的距离，分别记为 和 。然后枚举所有的公共点 ，然后求出 $\max(d_1[i], d_2[i])$，取其中的最小值即可。 时间复杂度 ，空间复杂度 。其中 为节点个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。
有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。
同时给你两个节点 node1 和 node2 。
请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。
注意 edges 可能包含环。
示例 1：
输入：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.length2 <= n <= 105-1 <= edges[i] < nedges[i] != i0 <= node1, node2 < n
解题思路
方法一：BFS + 枚举公共点
我们可以先用 BFS 求出从 和 分别到达每个点的距离，分别记为 和 。然后枚举所有的公共点 ，然后求出 ，取其中的最小值即可。
时间复杂度 ，空间复杂度 。其中 为节点个数。
相似题目：
class Solution:
def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
def f(i):
dist = [inf] * n
dist[i] = 0
q = deque([i])
while q:
i = q.popleft()
for j in g[i]:
if dist[j] == inf:
dist[j] = dist[i] + 1
q.append(j)
return dist
g = defaultdict(list)
for i, j in enumerate(edges):
if j != -1:
g[i].append(j)
n = len(edges)
d1 = f(node1)
d2 = f(node2)
ans, d = -1, inf
for i, (a, b) in enumerate(zip(d1, d2)):
if (t := max(a, b)) < d:
d = t
ans = i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for knowledge of graph traversal algorithms, specifically DFS.
- question_mark
Test understanding of minimizing distances in a graph traversal context.
- question_mark
Check for efficiency in handling large graphs with the constraint of up to 100,000 nodes.
常见陷阱
外企场景- error
Failing to handle graphs with nodes having no outgoing edges properly.
- error
Not correctly calculating the maximum distance between two nodes.
- error
Assuming that the closest node will always be a direct neighbor of either `node1` or `node2`.
进阶变体
外企场景- arrow_right_alt
Consider graphs with more complex structures, like cycles or disconnected components.
- arrow_right_alt
Handle multiple test cases efficiently without redundant recalculation.
- arrow_right_alt
Extend the problem to find the closest node for multiple source nodes, not just two.