1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| from collections import defaultdict
from typing import List
"""
In a town, there are N people labelled from 1 to N.
There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a
trusts the person labelled b.
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
"""
class Solution:
def _filterForJudge(self, N, trust_dict):
no_trustees = None
for i in range(1, N + 1):
person_trusted = trust_dict.get(i, set())
if len(person_trusted) == 0:
if no_trustees is None:
no_trustees = i
else:
return None
return no_trustees
def findJudge(self, N: int, trust: List[List[int]]) -> int:
trust_dict = defaultdict(set)
for i in trust:
trust_dict[i[0]].add(i[1])
# The town judge trusts nobody.
no_trustee = self._filterForJudge(N, trust_dict)
if no_trustee:
# Everybody trusts the town judge.
people_who_trust = 0
for p in trust_dict.items():
# Check if the person trusts the town judge.
if no_trustee in p[1]:
people_who_trust += 1
if people_who_trust == N-1:
return no_trustee
return -1
if __name__ == '__main__':
s = Solution()
print(s.findJudge(2, [[1,2]]))
print(s.findJudge(3, [[1,3],[2,3]]))
print(s.findJudge(3, [[1,3],[2,3],[3,1]]))
print(s.findJudge(3, [[1,2],[2,3]]))
print(s.findJudge(4, [[1,3],[1,4],[2,3],[2,4],[4,3]]))
|