Town Judge

https://leetcode.com/explore/featured/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3325/

brutal force:

from collections import defaultdict
class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        if N==1 and len(trust) == 0:
            return 1
        d = defaultdict(list)
        s = set()
        for edge in trust:
            a,b = edge
            d[b].append(a)
            s.add(a)
        res = []
        for k,v in d.items():
            if len(v) == N-1:
                res.append(k)
        
        if len(res) != 1:
            return -1
        if res[0] in s:
            return -1
        return res[0]

图论的方法

indegrees & outdegrees

如果被人相信是indegree，相信别人是outdegree，town judge的indegree是N-1， outdegree是0

from collections import defaultdict
class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        indegrees = [0] * (N+1)
        outdegrees = [0] * (N+1)
        for edge in trust:
            a,b = edge
            outdegrees[a]+=1
            indegrees[b]+=1
        res = []
        for i in range(1,N+1):
            if outdegrees[i] == 0 and indegrees[i] == N-1:
                res.append(i)
        if len(res) != 1:
            return -1
        return res[0]