圖論應用: 尋找法官 Find the Town Judge_Leetcode #997
題目敘述
題目會給定一個參數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
trustare unique.
所有信任關係都是獨一無二的，不會重複。
ai!= bi
不會有自我指向邊(不會有[a, a]，a信任a 這種輸入)
1 <= ai, bi<= n
所有信任關係的ID都是合法範圍內1~n的數字。
演算法 圖論 + Degree判定
可以把整個問題轉換為圖論的Degree判定問題:
把每個村民視為一個節點，
村民a信任村民b代表節點a到結點b有一條指向邊。
題目說成為法官的條件:
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.法官不信任別人。
等價於圖論上的
- 每個節點(除了法官節點之外)，都有一條指向邊指向法官節點。
- 法官節點沒有向外的邊(no out-going edge)。
Reference:
