【第二十一天 - Graph 题目分析】

• 先简单回顾一下，今天预计分析的题目： 997. Find the Town Judge

• 题目连结：https://leetcode.com/problems/find-the-town-judge/

• 题目叙述：

  • 如果真的有法官，则法官会满足这几个条件：
    • 这位法官不会相信任何人。
    • 法官以外的所有人，都相信法官。
    • 整个小镇只会恰有一个人满足这些条件。
  • 给定镇民之间的信任关系，要找出法官是谁。
  • 一个小镇中有编号 1 ~ n 的人，谣传这些人之中，有一个人是秘密的小镇法官。
    

• 测资的 Input/Output

  • input 为 小镇上有 n 个人 与 纪录了信任关系的二维阵列 trust
  • output 需要回传谁是小镇的法官，若无则回传 -1
    

• 若法官存在，则相信他者为 n - 1 人，而他相信者为 0 人

• 因此先用直接用回圈扫过 trust ，纪录每个人被相信与相信他人的数量

# 每个 Person 都纪录会纪录 [被别人相信的次数, 相信别人的次数]
person = [[0, 0] for i in range(n + 1)]

for i in trust:
    # 取得一比信任关系 (a 信任 b)
    a, b = i

    # a 信任他人的数量 + 1
    person[a][1] += 1

    # b 被信任的数量 + 1
    person[b][0] += 1

- 如图，由於镇民是由 1 开始编号，为了方便，我们开了 n + 1 长度的阵列用来记录镇民资料。
- 每个 person 的第零个栏位用来记录被信任的次数，第一个栏位纪录信任他人的次数。

• 再用一次回圈扫过所有镇民，找出符合法官条件者即可。

for i in range(1, n + 1):
    if person[i][1] == 0 and person[i][0] == n - 1:
        # 若第 i 位镇民相信 0 人，且被 n - 1 人相信，则第 i 位就是法官
        return i

• 若无满足条件者，则不存在法官。

return -1

• 完整程序码如下

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
#                [BeTrustedNum, TrustOtherNum]
        person = [[0, 0] for i in range(n + 1)]

        for i in trust:
            a, b = i
#           有信任别人就加1
            person[a][1] += 1
#           有被人信任就加1
            person[b][0] += 1

        for i in range(1, n + 1):
#           满足不信任其他人 和 被全部的人信任，则为法官
            if person[i][1] == 0 and person[i][0] == n - 1:
                return i

        return -1