圖論應用: 尋找法官 Find the Town Judge_Leetcode #997

Tingey Injury Law Firm null on Unsplash

題目敘述

題目會給定一個參數n代表人口總數，和對應的信任關係陣列trust，陣列元素都是pair，都以[a, b]的形式呈現，代表a信任b。

要求我們找出法官是誰，返回法官的ID?

成為法官的條件:

1.每個人(除了法官自己之外)都信任法官。

2.法官不信任別人。

題目的原文敘述

測試範例

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2
1信任2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3
1信任3
2信任3​

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
1信任3
2信任3
3信任2 (違反"法官不信任別人"的規則，3無法成為法官)​

約束條件

Constraints:

• 1 <= n <= 1000

人口總數介於1~1000之間

• 0 <= trust.length <= 10^4

信任關係陣列長度介於0~一萬之間。

• trust[i].length == 2

信任關係陣列元素以pair的方式呈現。

• All the pairs of trust are unique.

所有信任關係都是獨一無二的，不會重複。

• ai != bi

不會有自我指向邊(不會有[a, a]，a信任a 這種輸入)

• 1 <= ai, bi <= n

所有信任關係的ID都是合法範圍內1~n的數字。

演算法 圖論 + Degree判定

可以把整個問題轉換為圖論的Degree判定問題:

把每個村民視為一個節點，

村民a信任村民b代表節點a到結點b有一條指向邊。

題目說成為法官的條件:

1.每個人(除了法官自己之外)都信任法官。

2.法官不信任別人。

等價於圖論上的

1. 每個節點(除了法官節點之外)，都有一條指向邊指向法官節點。
2. 法官節點沒有向外的邊(no out-going edge)。

因此，我們可以以知道，法官節點的淨輸入度(Net in-degee)

=總輸入度 - 總輸出度

= Total in degree - Total out degree

= (n-1) - 0

= n-1

就用這條關係式，去找出法官是誰。

這題剛好以前錄過教學影片，提供給讀者作為參考

程式碼 圖論 + Degree判定

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:

        # 0 is dummy cell
        # key: person id
        # value: total in degree - total out degree
        net_in_degree = [ 0 for _ in range(n+1) ]

        for person_a, person_b in trust:
            
            # a trust b <=> indegree of b increment, inegree of a decrement
            net_in_degree[person_b] += 1
            net_in_degree[person_a] -= 1
        
        # Town judge <=> net indegree = n-1
        for p in range(1, n+1):
            if net_in_degree[p] == (n-1):
                return p
        
        return -1

複雜度分析 圖論 + Degree判定

時間複雜度:

掃描每隔節點耗時O(n)，掃描每個信任關係耗時O(t)。

當輸入是稠密圖時，可能會有很多信任關係(相當於有很多條邊)，可能高達C(n,2) = O(n^2)

總共所需時間為O(n) + O(t) = 當輸入時是稠密圖時，可能高達O(n^2)

空間複雜度:

需要一個net_in_degree表格，計入每個節點的淨輸入度，所需空間為O(n)。

關鍵知識點

可以把整個問題轉換為圖論的Degree判定問題:

把每個村民視為一個節點，

村民a信任村民b代表節點a到結點b有一條指向邊。

題目說成為法官的條件:

1.每個人(除了法官自己之外)都信任法官。

2.法官不信任別人。

等價於圖論上的

1. 每個節點(除了法官節點之外)，都有一條指向邊指向法官節點。
2. 法官節點沒有向外的邊(no out-going edge)。

Reference:

[1] Find the Town Judge - LeetCode