Pular para o conteúdo

O juiz de confiança da cidade

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

A missão

Problema

Uma cidade tem n pessoas rotuladas de 1 a n e uma lista de pares em que o par a, b significa que a confia em b. Exatamente uma pessoa pode ser o juiz: o juiz não confia em ninguém, e todas as outras pessoas da cidade confiam no juiz. Retorne o rótulo do juiz, ou -1 quando essa pessoa não existir.

Exemplos

Input:  n = 2, trust = [[1, 2]]
Output: 2
Por quê: a pessoa 2 não confia em ninguém e recebe a confiança da única outra pessoa
Input:  n = 3, trust = [[1, 3], [2, 3], [3, 1]]
Output: -1
Por quê: a pessoa 3 recebe a confiança de todos, mas também confia em alguém
Input:  n = 1, trust = []
Output: 1
Por quê: edge case: o único morador satisfaz as duas regras trivialmente

Dicas

0 / 3

Tempo-alvo
O(n + p)
Espaço-alvo
O(n)

Restrições

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

Travou na ideia, e não no código? O básico de grafos explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado