すべてのノードから参照されるノードの検出
概要
- できるだけ小さい計算回数で行うには、ランダムでノードを選択し、そこから辿れるだけたどった場合の末端が候補となる
具体的な実装例
- すべての人から知られている有名人を検出する
- 自分自身をすべての人は知っているとする
- 有名人は自分自身以外に何も知らない
class Solution:
def findCelebrity(self, n: int) -> int:
self.n = n
celebrity_candidate = 0
for i in range(1, n):
if knows(celebrity_candidate, i):
celebrity_candidate = i
if self.is_celebrity(celebrity_candidate):
return celebrity_candidate
return -1
def is_celebrity(self, i):
for j in range(self.n):
if i == j: continue
if knows(i, j) or not knows(j, i):
return False
return True