997.找到小镇的法官

原题

一、与277.搜寻名人 类似

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        s = set()
        # 将所有信任关系以元组形式存入set
        for t1, t2 in trust:
            s.add((t1, t2))
        cand = 1
        other = 2
        while other <= n:
            if (cand, other) in s or (other, cand) not in s:
                cand = other
            other += 1
        for i in range(1, n+1):
            if i == cand:
                continue
            if (cand, i) in s or (i, cand) not in s:
                return -1
        return cand

二、有向图

这里用有向图不会超时，因为所有的边关系都已给出在trust数组中，不像277题要遍历所有两两节点关系才能得到图的全部边关系。

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        inDeg = [0] * (n+1)     # 所有节点入度
        outDeg = [0] * (n+1)    # 所有节点出度
        for a, b in trust:
            outDeg[a] += 1
            inDeg[b] += 1
        for i in range(1, n+1):
            if inDeg[i] == n-1 and outDeg[i] == 0:
                return i 
        return -1