Saltar al contenido

El juez de confianza del pueblo

Fácil#degree-counting#directed-graph~15 min

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

Tiempo objetivo
O(n + p)
Espacio objetivo
O(n)

Restricciones

  • people are labelled 1 to n
  • at most one person can be the judge

¿Lo que te frena es la idea y no el código? Fundamentos de grafos lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio