https://leetcode.com/problems/find-the-town-judge/
graphの問題で、trust のペア, [a, b] は a から b に向かう directed edge である。
例えば、 N = 5 で trust trust = [[1,3],[2,3],[4,3],[4,1],[5,3],[5,1],[5,4]] の場合下記のような graph になる。
3 は 1,2,4,5 から信頼されていて、 誰も信頼していない。 そのため、judge は 3 になる。
この graph theory の、 outdegree の辺は、 その人が他の人を信頼している数になる。
indegree の辺は他の人から信頼されている数になる。
そのため indegree と outdegree によって誰が judge か判断できる。
judge は outdegree が 0 で indegree が N - 1 となる。
trust をループして全員の indegree, outdegree の数を調査できる。
indegree = [0] * (N + 1)
outdegree = [0] * (N + 1)
for a, b in trust:
outdegree[a] += 1
indegree[b] += 1
そして、1 ～ N 人全員をループして、チェックすれば、 judge がわかる。
for i in range(1, N + 1):
if indegree[i] == N - 1 and outdegree[i] == 0:
return i
return -1
Time complexity: O(E)
Mem complexity: O(n)
def findJudge(self, N: int, trust: List[List[int]]) -> int:
if len(trust) < N - 1:
return -1
indegree = [0] * (N + 1)
outdegree = [0] * (N + 1)
for a, b in trust:
outdegree[a] += 1
indegree[b] += 1
for i in range(1, N + 1):
if indegree[i] == N - 1 and outdegree[i] == 0:
return i
return -1