Maximizar Cantidad de Nodos Objetivos al Unir Árboles I
Existen dos árboles no dirigidos con n y m nodos, con etiquetas distintas en los rangos [0, n - 1] y [0, m - 1], respectivamente.
Se te dan dos arreglos de enteros 2D edges1 y edges2 de longitudes n - 1 y m - 1, respectivamente, donde edges1[i] = [ai, bi] indica que hay una arista entre los nodos y en el primer árbol y indica que hay una arista entre los nodos y en el segundo árbol. También se te da un entero k.
El nodo u es objetivo para el nodo v si el número de aristas en la ruta desde u hasta v es menor o igual a k. Nota que un nodo siempre es objetivo para sí mismo.
Devuelve un arreglo de n enteros answer, donde answer[i] es el número máximo posible de nodos objetivo para el nodo i del primer árbol si tienes que conectar un nodo del primer árbol con otro nodo del segundo árbol.
Nota que las consultas son independientes entre sí. Es decir, para cada consulta eliminarás la arista añadida antes de proceder a la siguiente consulta.
Ejemplos
Ejemplo 1:
Input: edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]], k = 2 Output: [9,7,9,8,8] Explicación: Para i = 0, conecta el nodo 0 del primer árbol al nodo 0 del segundo árbol. Para i = 1, conecta el nodo 1 del primer árbol al nodo 0 del segundo árbol. Para i = 2, conecta el nodo 2 del primer árbol al nodo 4 del segundo árbol. Para i = 3, conecta el nodo 3 del primer árbol al nodo 4 del segundo árbol. Para i = 4, conecta el nodo 4 del primer árbol al nodo 4 del segundo árbol.
Ejemplo 2:
Input: edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]], k = 1 Output: [6,3,3,3,3] Explicación: Para cada i, conecta el nodo i del primer árbol con cualquier nodo del segundo árbol.
Soluciones
Python
from collections import deque
class Solution:
def BFS(self, start, adj, k):
q = deque()
q.append((start, -1))
count = 0
while q and k >= 0:
size = len(q)
count += size
for _ in range(size):
u, parent = q.popleft()
for v in adj[u]:
if v != parent:
q.append((v, u))
k -= 1
return count
def maxTargetNodes(self, edges1, edges2, k):
m = len(edges1) + 1
n = len(edges2) + 1
# Construir listas de adyacencia para el árbol 1
adj1 = [[] for _ in range(m)]
for u, v in edges1:
adj1[u].append(v)
adj1[v].append(u)
# Construir listas de adyacencia para el árbol 2
adj2 = [[] for _ in range(n)]
for u, v in edges2:
adj2[u].append(v)
adj2[v].append(u)
# Preprocesamiento: Encontrar el mejor nodo en el Árbol-2
best = 0
for i in range(n):
connections = self.BFS(i, adj2, k - 1)
best = max(best, connections)
# Construir respuesta
res = []
for i in range(m):
connections = self.BFS(i, adj1, k)
res.append(connections + best)
return res