Encontrar el Nodo más Cercado a Dos Nodos
Se te da un grafo dirigido de n nodos numerados del 0 al n - 1, donde cada nodo tiene como máximo una arista saliente.
El grafo está representado con un arreglo indexado desde 0 llamado edges de tamaño n, indicando que hay una arista dirigida del nodo i al nodo edges[i]. Si no hay arista saliente desde i, entonces edges[i] == -1.
También se te dan dos enteros node1 y node2.
Devuelve el índice del nodo que puede ser alcanzado desde ambos node1 y node2, tal que el máximo entre la distancia de node1 a ese nodo y de node2 a ese nodo sea minimizado. Si hay múltiples respuestas, devuelve el nodo con el índice más pequeño, y si no existe una respuesta posible, devuelve -1.
Nota que edges puede contener ciclos.
Ejemplos
Ejemplo 1:
Input: edges = [2,2,3,-1], node1 = 0, node2 = 1 Output: 2 Explicación: La distancia del nodo 0 al nodo 2 es 1, y la distancia del nodo 1 al nodo 2 es 1. El máximo de esas dos distancias es 1. Se puede probar que no podemos obtener un nodo con una distancia máxima menor que 1, así que devolvemos el nodo 2.
Ejemplo 2:
Input: edges = [1,2,-1], node1 = 0, node2 = 2 Output: 2 Explicación: La distancia del nodo 0 al nodo 2 es 2, y la distancia del nodo 2 a sí mismo es 0. El máximo de esas dos distancias es 2. Se puede probar que no podemos obtener un nodo con una distancia máxima menor que 2, así que devolvemos el nodo 2.
Soluciones
Python
from collections import deque
class Solution:
def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
n = len(edges)
dist = [[-1, -1] for _ in range(n)]
dist[node1][0] = 0
dist[node2][1] = 0
q = deque()
q.append((node1, 0))
q.append((node2, 1))
while q:
curr, typ = q.popleft()
neighbor = edges[curr]
if neighbor != -1 and dist[neighbor][typ] == -1:
dist[neighbor][typ] = dist[curr][typ] + 1
q.append((neighbor, typ))
meeting_point = -1
min_distance = float('inf')
for i in range(n):
if dist[i][0] != -1 and dist[i][1] != -1:
curr_distance = max(dist[i][0], dist[i][1])
if curr_distance < min_distance:
min_distance = curr_distance
meeting_point = i
return meeting_point