Medium

题目描述

给定一个有 n 个节点的有向图，节点编号从 0 到 n - 1，每个节点最多有一条出边。

图用一个长度为 n 的 0 索引数组 edges 表示，表示从节点 i 到节点 edges[i] 有一条有向边。如果节点 i 没有出边，则 edges[i] == -1。

同时给定两个整数 node1 和 node2。

返回可以从 node1 和 node2 都能到达的节点索引，使得从 node1 到该节点的距离和从 node2 到该节点的距离中的最大值最小。如果有多个答案，返回索引最小的节点，如果不存在可能的答案，返回 -1。

注意图中可能包含环。

示例 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.length
  • 2 <= n <= 10^5
  • -1 <= edges[i] < n
  • edges[i] != i
  • 0 <= node1, node2 < n

解题思路

这道题要求找到两个起始节点都能到达的节点中，使得最大距离最小的那个节点。

解题思路

核心思想： 分别从两个起始节点进行BFS/DFS，计算到所有可达节点的最短距离，然后找到两个距离数组中都有值的节点，在这些节点中选择最大距离最小的。

算法步骤：

  1. 使用BFS或DFS从 node1 开始，计算到所有可达节点的最短距离
  2. 使用BFS或DFS从 node2 开始，计算到所有可达节点的最短距离
  3. 遍历所有节点，找到同时被两个起始节点到达的节点
  4. 在这些节点中，选择 max(dist1[i], dist2[i]) 最小的节点
  5. 如果有多个最优节点，选择索引最小的

实现细节：

  • 由于每个节点最多有一条出边，图的结构相对简单，可以用DFS实现
  • 需要处理环的情况，使用visited数组避免无限循环
  • 距离数组初始化为-1表示不可达，避免与距离0混淆

时间复杂度： O(n) - 每个节点最多访问一次 空间复杂度： O(n) - 存储距离数组和visited数组

代码实现

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n = edges.size();
        vector<int> dist1(n, -1), dist2(n, -1);
        
        // 计算从node1到各节点的距离
        dfs(edges, node1, dist1);
        // 计算从node2到各节点的距离
        dfs(edges, node2, dist2);
        
        int result = -1, minMaxDist = INT_MAX;
        
        // 寻找最优汇合点
        for (int i = 0; i < n; i++) {
            if (dist1[i] != -1 && dist2[i] != -1) {
                int maxDist = max(dist1[i], dist2[i]);
                if (maxDist < minMaxDist) {
                    minMaxDist = maxDist;
                    result = i;
                }
            }
        }
        
        return result;
    }
    
private:
    void dfs(vector<int>& edges, int start, vector<int>& dist) {
        int curr = start;
        int d = 0;
        
        while (curr != -1 && dist[curr] == -1) {
            dist[curr] = d++;
            curr = edges[curr];
        }
    }
};

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        
        def calculateDistances(start):
            dist = [-1] * n
            curr = start
            d = 0
            
            while curr != -1 and dist[curr] == -1:
                dist[curr] = d
                d += 1
                curr = edges[curr]
            
            return dist
        
        # 计算从两个起始节点到各节点的距离
        dist1 = calculateDistances(node1)
        dist2 = calculateDistances(node2)
        
        result = -1
        min_max_dist = float('inf')
        
        # 寻找最优汇合点
        for i in range(n):
            if dist1[i] != -1 and dist2[i] != -1:
                max_dist = max(dist1[i], dist2[i])
                if max_dist < min_max_dist:
                    min_max_dist = max_dist
                    result = i
        
        return result

public class Solution {
    public int ClosestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.Length;
        int[] dist1 = new int[n];
        int[] dist2 = new int[n];
        Array.Fill(dist1, -1);
        Array.Fill(dist2, -1);
        
        // 计算从两个起始节点到各节点的距离
        CalculateDistances(edges, node1, dist1);
        CalculateDistances(edges, node2, dist2);
        
        int result = -1;
        int minMaxDist = int.MaxValue;
        
        // 寻找最优汇合点
        for (int i = 0; i < n; i++) {
            if (dist1[i] != -1 && dist2[i] != -1) {
                int maxDist = Math.Max(dist1[i], dist2[i]);
                if (maxDist < minMaxDist) {
                    minMaxDist = maxDist;
                    result = i;
                }
            }
        }
        
        return result;
    }
    
    private void CalculateDistances(int[] edges, int start, int[] dist) {
        int curr = start;
        int d = 0;
        
        while (curr != -1 && dist[curr] == -1) {
            dist[curr] = d++;
            curr = edges[curr];
        }
    }
}

var closestMeetingNode = function(edges, node1, node2) {
    const n = edges.length;
    
    function calculateDistances(start) {
        const dist = new Array(n).fill(-1);
        let curr = start;
        let d = 0;
        
        while (curr !== -1 && dist[curr]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每个节点最多被访问一次，总共需要遍历两次图
空间复杂度O(n)需要两个距离数组存储从起始节点到各节点的距离