997. Find the Town Judge

Question

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Solution

题目可以转换为计算各个顶点的入度和出度。

遍历每条边，并计算边上两个顶点的出度和入度。
如果某个节点的入度为n-1，出度为0，则符合有法官的条件。
否则没有法官，返回-1。

Code

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegrees = new int[n];
        int[] outDegrees = new int[n];
        
        for(int[] edge : trust){
            outDegrees[edge[0]-1]++;
            inDegrees[edge[1]-1]++;
        }
        for(int i = 0; i < n; i++){
            if(outDegrees[i] == 0 && inDegrees[i] == n-1) return i+1;
        }
        return -1;
    }
}