Graph

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 がわかる。...