[数据结构与算法]不是吧不是吧日刷也算刷-LeetCode-997-寻找镇法官

997题:find the town judge

题目：

在一个小镇上，有N个人，编号从1到N，传言有个人是个秘密的镇法官。

如果传言是真，镇法官需要符合下面的条件：

1. 镇法官不相信任何人

2. 任何人(除了镇法官本人)都相信镇法官

3. 只有一个人满足1和2两个条件

给定一个信任列表trust，trust[i] = [a,b]表示a信任b。

如果存在镇法官，返回镇法官的编号，否则返回-1。

备注：

1. 1 <= N <= 1000

2. trust.length <= 10000

3. trust[i] are all different

4. trust[i][0] != trust[i][1]

5. 1 <= trust[i][0], trust[i][1] <= N

解题思路

把所有的信任关系看做图，所有的信任对trust[]看做有向边。

某个点的入度-出度=N-1，这个点所在的人就是镇法官

public int findJudge(int N, in[][] trust){
    int[] count = new int[N+1];
    for(int[] t : trust){
        count[t[0]]--;
        count[t[1]]++;
    }
    for(int i = 1;i<=N;++i){
        if(count[i] == N -1){
            return i;
        }
    }
    return -1;
}