İçeriğe geç

Kasabanın güvenilen yargıcı

Kolay#degree-counting#directed-graph~15 dk

Görev tanımı

Problem

Bir kasabada 1'den n'ye kadar etiketlenmiş n kişi ve a, b çiftinin a'nın b'ye güvendiği anlamına geldiği bir çift listesi var. Tam olarak bir kişi yargıç olabilir: yargıç kimseye güvenmez ve kasabadaki diğer herkes yargıca güvenir. Yargıcın etiketini döndür; böyle biri yoksa -1 döndür.

Örnekler

Input:  n = 2, trust = [[1, 2]]
Output: 2
Neden: 2 numaralı kişi kimseye güvenmiyor ve diğer tek kişi ona güveniyor
Input:  n = 3, trust = [[1, 3], [2, 3], [3, 1]]
Output: -1
Neden: 3 numaralı kişiye herkes güveniyor ama o da birine güveniyor
Input:  n = 1, trust = []
Output: 1
Neden: edge case: tek sakin iki kuralı da boş yere sağlıyor

İpuçları

0 / 3

Hedef zaman
O(n + p)
Hedef alan
O(n)

Kısıtlar

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

Kodda değil de fikirde mi takıldın? Graf temelleri bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case