找到小镇的法官

题目

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

小镇法官不会信任任何人。
每个人（除了小镇法官）都信任这位小镇法官。
只有一个人同时满足属性 1 和属性 2 。
给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

思路

把小镇里的人全部看成一个有向图中的点，那么题干中trust[ai,bi]就表示从ai到bi连一条有向边。这样一来，我们只需要判断是否存在一个入度为n-1而出度为0的点就可以了。

代码

public int findProphet(int n, int[][] trust) {
    int[] inDegrees = new int[n];
    int[] outDegrees = new int[n];
    for (int i = 0; i < trust.length; ++i) {
        for (int j = 0; j < trust[i].length; ++j) {
            if (trust[i][j] == 1) {
                ++outDegrees[i];
                ++inDegrees[j];
            }
        } 
    }
    for (int i = 0; i < inDegrees.length; ++i) {
        if (inDegrees[i] == n-1 && outDegrees[i] == 0) {
            return i;
        }
    }
    return -1;
}