Question

2359. Find Closest Node to Given Two Nodes

中文文档

Description

You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.

The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from i, then edges[i] == -1.

You are also given two integers node1 and node2.

Return _the index of the node that can be reached from both _node1_ and _node2_, such that the maximum between the distance from _node1_ to that node, and from _node2_ to that node is minimized_. If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1.

Note that edges may contain cycles.

 

Example 1:

Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Explanation: The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1.
The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.

Example 2:

Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Explanation: The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0.
The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.

 

Constraints:

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

Solutions

Solution 1

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;
}

Solution 2

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
}