[Leetcode][997. 找到小镇的法官] 图论，计算各节点的入度和出度

By Long Luo

Leetcode 997. 找到小镇的法官 题解。

方法一：图论

思路与算法：

1. 如果存在法官，那么所有人都会信任法官，在结合条件$1$，可以得出信任法官的人数为$n - 1$；
2. 如果不存在法官，那么也可能存在某些人被所有人信任，这个人的信任人数也为$n - 1$，但是他也会信任别人；
3. 可以以此作为区分other和judge的条件，假设每个人都有信任值，那么定义一个数组长度为$n$，用来存放$n$个人的信任值:

• 如果一个人信任了别人，那么这个人的信任值$-1$
• 如果一个人被别人信任，那么这个人的信任值$+1$

所以：

1. 当一个人被所有人信任，并且他没有信任其它人时，这个人的信任值就是$n - 1$，那么此人就是法官；
2. 当一个人被所有人信任，但是他也信任了其他人时，这个人的信任值$< n - 1$。
   其它情况下，每个人的信任值都会小于$n - 1$。

public int findJudge(int N, int[][] trust) {
	if (N <= 0) {
		return -1;
	} else if (N == 1) {
		return 1;
	}

	// [0]: In  [1]: Out
	int[][] count = new int[N][2];
	for (int[] item : trust) {
		count[item[0] - 1][1]++;
		count[item[1] - 1][0]++;
	}

	for (int i = 0; i < N; i++) {
		if (count[i][0] == N - 1 && count[i][1] == 0) {
			return i + 1;
		}
	}

	return -1;
}

之后看来别人的题解才知道这道题其实考察的是图论的知识。

本题需要用到有向图中节点的入度和出度的概念。在有向图中，一个节点的入度是指向该节点的边的数量；而一个节点的出度是从该节点出发的边的数量。
题干描述了一个有向图。每个人是图的节点，$\textit{trust}$的元素$\textit{trust}[i]$是图的有向边，从$\textit{trust}[i][0]$指向$\textit{trust}[i][1]$。我们可以遍历 $\textit{trust}$，统计每个节点的入度和出度，存储在$\textit{inDegrees}$和$\textit{outDegrees}$中。
根据题意，在法官存在的情况下，法官不相信任何人，每个人（除了法官外）都信任法官，且只有一名法官。因此法官这个节点的入度是$n - 1$, 出度是$0$。
我们可以遍历每个节点的入度和出度，如果找到一个符合条件的节点，由于题目保证只有一个法官，我们可以直接返回结果；如果不存在符合条件的点，则返回$-1$。

复杂度分析

• 时间复杂度：$O(n+m)$，其中$m$是$\textit{trust}$的长度。首先需要遍历$\textit{trust}$计算出$\textit{inDegrees}$和$\textit{outDegrees}$，然后需要遍历$\textit{inDegrees}$和$\textit{outDegrees}$来确定法官。

• 空间复杂度：$O(n)$。记录各个节点的入度和出度需要$O(n)$的空间。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗