El juez de confianza del pueblo
La misión
Problema
Un pueblo tiene n personas etiquetadas del 1 al n y una lista de pares donde el par a, b significa que a confía en b. Solo una persona puede ser el juez: el juez no confía en nadie, y todas las demás personas del pueblo confían en el juez. Devuelve la etiqueta del juez, o -1 si esa persona no existe.
Ejemplos
Input: n = 2, trust = [[1, 2]]
Output: 2
Por qué: la persona 2 no confía en nadie y la única otra persona confía en ella
Input: n = 3, trust = [[1, 3], [2, 3], [3, 1]]
Output: -1
Por qué: todos confían en la persona 3, pero ella también confía en alguien
Input: n = 1, trust = []
Output: 1
Por qué: caso límite: el único habitante cumple trivialmente ambas reglas
Pistas
0 / 3
Aquí no busques caminos. Las dos reglas tratan de cuántas flechas tocan a una persona, no de adónde puedes viajar.
Cada par manda una flecha que sale de a y entra en b. Contar las flechas entrantes y salientes de cada persona basta para comprobar ambas reglas.
Lleva un solo número por persona: suma uno cuando alguien confía en ella y resta uno cuando ella confía en alguien. El juez es la única persona cuyo número puede llegar a uno menos que la población, así que busca ese valor e informa que no hay juez si nadie lo tiene.
- Tiempo objetivo
- O(n + p)
- Espacio objetivo
- O(n)
Restricciones
- people are labelled 1 to n
- at most one person can be the judge
Solución
Ambas reglas son condiciones de grado, así que un solo conteo por persona las responde a la vez: recibir confianza suma uno y confiar en alguien resta uno. Solo una persona en quien confían los otros n-1 y que no confía en nadie puede llegar a un puntaje de n-1, porque cualquier confianza saliente lo bajaría por debajo de ese máximo. Basta con una pasada sobre los pares y otra sobre las personas. El tiempo es O(n + p) para p pares, y el espacio es O(n).
def find_judge(n, trust):
score = [0] * (n + 1) # times trusted minus times trusting
for a, b in trust:
score[a] -= 1
score[b] += 1
for person in range(1, n + 1):
if score[person] == n - 1: # trusted by all the others, trusts nobody
return person
return -1
print(find_judge(2, [[1, 2]])) # -> 2
print(find_judge(3, [[1, 3], [2, 3], [3, 1]])) # -> -1
print(find_judge(1, [])) # -> 1¿Lo que te frena es la idea y no el código? Fundamentos de grafos lo explica.