Question

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

English Version

题目描述

给你一个 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.length
• 2 <= n <= 105
• -1 <= edges[i] < n
• edges[i] != i
• 0 <= node1, node2 < n

解法

方法一：BFS + 枚举公共点

我们可以先用 BFS 求出从 $node1$ 和 $node2$ 分别到达每个点的距离，分别记为 $d_1$ 和 $d_2$。然后枚举所有的公共点 $i$，然后求出 $\max(d_1[i], d_2[i])$，取其中的最小值即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为节点个数。

相似题目：

• 2203.得到要求路径的最小带权子图

class Solution:
  def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
    def dijkstra(i):
      dist = [inf] * n
      dist[i] = 0
      q = [(0, i)]
      while q:
        i = heappop(q)[1]
        for j in g[i]:
          if dist[j] > dist[i] + 1:
            dist[j] = dist[i] + 1
            heappush(q, (dist[j], j))
      return dist

    g = defaultdict(list)
    for i, j in enumerate(edges):
      if j != -1:
        g[i].append(j)
    n = len(edges)
    d1 = dijkstra(node1)
    d2 = dijkstra(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

class Solution {
  private int n;
  private List<Integer>[] g;

  public int closestMeetingNode(int[] edges, int node1, int node2) {
    n = edges.length;
    g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n; ++i) {
      if (edges[i] != -1) {
        g[i].add(edges[i]);
      }
    }
    int[] d1 = dijkstra(node1);
    int[] d2 = dijkstra(node2);
    int d = 1 << 30;
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      int t = Math.max(d1[i], d2[i]);
      if (t < d) {
        d = t;
        ans = i;
      }
    }
    return ans;
  }

  private int[] dijkstra(int i) {
    int[] dist = new int[n];
    Arrays.fill(dist, 1 << 30);
    dist[i] = 0;
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    q.offer(new int[] {0, i});
    while (!q.isEmpty()) {
      var p = q.poll();
      i = p[1];
      for (int j : g[i]) {
        if (dist[j] > dist[i] + 1) {
          dist[j] = dist[i] + 1;
          q.offer(new int[] {dist[j], j});
        }
      }
    }
    return dist;
  }
}

class Solution {
public:
  int closestMeetingNode(vector<int>& edges, int node1, int node2) {
    int n = edges.size();
    vector<vector<int>> g(n);
    for (int i = 0; i < n; ++i) {
      if (edges[i] != -1) {
        g[i].push_back(edges[i]);
      }
    }
    const int inf = 1 << 30;
    using pii = pair<int, int>;
    auto dijkstra = [&](int i) {
      vector<int> dist(n, inf);
      dist[i] = 0;
      priority_queue<pii, vector<pii>, greater<pii>> q;
      q.emplace(0, i);
      while (!q.empty()) {
        auto p = q.top();
        q.pop();
        i = p.second;
        for (int j : g[i]) {
          if (dist[j] > dist[i] + 1) {
            dist[j] = dist[i] + 1;
            q.emplace(dist[j], j);
          }
        }
      }
      return dist;
    };
    vector<int> d1 = dijkstra(node1);
    vector<int> d2 = dijkstra(node2);
    int ans = -1, d = inf;
    for (int i = 0; i < n; ++i) {
      int t = max(d1[i], d2[i]);
      if (t < d) {
        d = t;
        ans = i;
      }
    }
    return ans;
  }
};

func closestMeetingNode(edges []int, node1 int, node2 int) int {
  n := len(edges)
  g := make([][]int, n)
  for i, j := range edges {
    if j != -1 {
      g[i] = append(g[i], j)
    }
  }
  const inf int = 1 << 30
  dijkstra := func(i int) []int {
    dist := make([]int, n)
    for j := range dist {
      dist[j] = inf
    }
    dist[i] = 0
    q := hp{}
    heap.Push(&q, pair{0, i})
    for len(q) > 0 {
      i := heap.Pop(&q).(pair).i
      for _, j := range g[i] {
        if dist[j] > dist[i]+1 {
          dist[j] = dist[i] + 1
          heap.Push(&q, pair{dist[j], j})
        }
      }
    }
    return dist
  }
  d1 := dijkstra(node1)
  d2 := dijkstra(node2)
  ans, d := -1, inf
  for i, a := range d1 {
    b := d2[i]
    t := max(a, b)
    if t < d {
      d = t
      ans = i
    }
  }
  return ans
}

type pair struct{ d, i int }
type hp []pair

func (h hp) Len() int       { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].d < h[j].d }
func (h hp) Swap(i, j int)    { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)    { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any      { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

function closestMeetingNode(edges: number[], node1: number, node2: number): number {
  const n = edges.length;
  const g = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; ++i) {
    if (edges[i] != -1) {
      g[i].push(edges[i]);
    }
  }
  const inf = 1 << 30;
  const f = (i: number) => {
    const dist = new Array(n).fill(inf);
    dist[i] = 0;
    const q: number[] = [i];
    while (q.length) {
      i = q.shift();
      for (const j of g[i]) {
        if (dist[j] == inf) {
          dist[j] = dist[i] + 1;
          q.push(j);
        }
      }
    }
    return dist;
  };
  const d1 = f(node1);
  const d2 = f(node2);
  let ans = -1;
  let d = inf;
  for (let i = 0; i < n; ++i) {
    const t = Math.max(d1[i], d2[i]);
    if (t < d) {
      d = t;
      ans = i;
    }
  }
  return ans;
}

方法二

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

class Solution {
  private int n;
  private List<Integer>[] g;

  public int closestMeetingNode(int[] edges, int node1, int node2) {
    n = edges.length;
    g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n; ++i) {
      if (edges[i] != -1) {
        g[i].add(edges[i]);
      }
    }
    int[] d1 = f(node1);
    int[] d2 = f(node2);
    int d = 1 << 30;
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      int t = Math.max(d1[i], d2[i]);
      if (t < d) {
        d = t;
        ans = i;
      }
    }
    return ans;
  }

  private int[] f(int i) {
    int[] dist = new int[n];
    Arrays.fill(dist, 1 << 30);
    dist[i] = 0;
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(i);
    while (!q.isEmpty()) {
      i = q.poll();
      for (int j : g[i]) {
        if (dist[j] == 1 << 30) {
          dist[j] = dist[i] + 1;
          q.offer(j);
        }
      }
    }
    return dist;
  }
}

class Solution {
public:
  int closestMeetingNode(vector<int>& edges, int node1, int node2) {
    int n = edges.size();
    vector<vector<int>> g(n);
    for (int i = 0; i < n; ++i) {
      if (edges[i] != -1) {
        g[i].push_back(edges[i]);
      }
    }
    const int inf = 1 << 30;
    using pii = pair<int, int>;
    auto f = [&](int i) {
      vector<int> dist(n, inf);
      dist[i] = 0;
      queue<int> q{{i}};
      while (!q.empty()) {
        i = q.front();
        q.pop();
        for (int j : g[i]) {
          if (dist[j] == inf) {
            dist[j] = dist[i] + 1;
            q.push(j);
          }
        }
      }
      return dist;
    };
    vector<int> d1 = f(node1);
    vector<int> d2 = f(node2);
    int ans = -1, d = inf;
    for (int i = 0; i < n; ++i) {
      int t = max(d1[i], d2[i]);
      if (t < d) {
        d = t;
        ans = i;
      }
    }
    return ans;
  }
};

func closestMeetingNode(edges []int, node1 int, node2 int) int {
  n := len(edges)
  g := make([][]int, n)
  for i, j := range edges {
    if j != -1 {
      g[i] = append(g[i], j)
    }
  }
  const inf int = 1 << 30
  f := func(i int) []int {
    dist := make([]int, n)
    for j := range dist {
      dist[j] = inf
    }
    dist[i] = 0
    q := []int{i}
    for len(q) > 0 {
      i = q[0]
      q = q[1:]
      for _, j := range g[i] {
        if dist[j] == inf {
          dist[j] = dist[i] + 1
          q = append(q, j)
        }
      }
    }
    return dist
  }
  d1 := f(node1)
  d2 := f(node2)
  ans, d := -1, inf
  for i, a := range d1 {
    b := d2[i]
    t := max(a, b)
    if t < d {
      d = t
      ans = i
    }
  }
  return ans
}