小镇法官：用入度与出度识别特殊节点

题面：小镇有 N 个人，trust[i] = [a, b] 表示 a 信任 b。如果法官存在，他不信任任何人，其他 N - 1 个人都信任他；返回法官编号，否则返回 -1。

1. 建模：从关系到度数

把每条信任关系看成有向边 a -> b：

a 的出度加一；
b 的入度加一。

法官的必要且充分条件是 inDegree - outDegree = N - 1。每条边只需一次更新，因此不必建立完整邻接表。这个“度数差”是一个可维护的不变量：处理前 k 条边后，score[x] 等于该节点已获得的入度数减去已产生的出度数。

2. JavaScript 实现

function findTownJudge(people, trust) {
  if (!Number.isInteger(people) || people < 1) {
    throw new RangeError('people must be a positive integer')
  }
  if (!Array.isArray(trust)) throw new TypeError('trust must be an array')

  const score = new Array(people + 1).fill(0)
  const seenRelations = new Set()

  for (const relation of trust) {
    if (!Array.isArray(relation) || relation.length !== 2) {
      throw new TypeError('each trust relation must be [from, to]')
    }
    const [from, to] = relation
    if (
      !Number.isInteger(from) ||
      !Number.isInteger(to) ||
      from < 1 ||
      from > people ||
      to < 1 ||
      to > people ||
      from === to
    ) {
      throw new RangeError('trust endpoints must be distinct people IDs')
    }
    const relationKey = `${from}->${to}`
    if (seenRelations.has(relationKey)) {
      throw new Error(`duplicate trust relation: ${relationKey}`)
    }
    seenRelations.add(relationKey)
    score[from] -= 1
    score[to] += 1
  }

  for (let person = 1; person <= people; person += 1) {
    if (score[person] === people - 1) return person
  }
  return -1
}

findTownJudge(2, [[1, 2]]) // 2
findTownJudge(3, [[1, 3], [2, 3]]) // 3
findTownJudge(3, [[1, 3], [2, 3], [3, 1]]) // -1
findTownJudge(1, []) // 1: 唯一的人自动满足条件

时间复杂度为 O(N + E)，E = trust.length；额外空间为 O(N)。如果题目保证输入合法，可以省略边界校验，但不应省略 N = 1 的判断逻辑。

3. 为什么度数差足够

若某人是法官，他的出度为 0、入度为 N - 1，所以差值为 N - 1。反过来，若某人的差值达到 N - 1，由于最多只能被其他 N - 1 人信任，必须同时满足入度 N - 1 和出度 0；因此他正是法官。任意自信任边或重复边都会破坏这个推导，若题面未保证“边唯一且不自环”，需要先去重或在契约中拒绝。

4. 邻接表版本与取舍

如果后续追问“还要输出谁信任谁”或“继续做图遍历”，应保留邻接表并分别统计入度、出度：空间 O(N + E)。单纯识别法官时，度数数组更省空间，也更容易证明。不要把 Array.findIndex 对数组索引 0 的默认结果误当成合法人物，遍历应从 1 开始。

5. 高频追问

Q: 为什么不是只找入度最大的点？

A: 入度最大不代表出度为零；例如环 1 -> 2 -> 3 -> 1 每人入度都为一，却没有法官。必须同时验证“被所有其他人信任”和“不信任任何人”。

Q: `trust` 为空时答案是什么？

A: N = 1 时唯一的人满足“其他 N - 1 = 0 人信任他且他不信任任何人”，返回 1；N > 1 时没有人达到 N - 1 的入度，返回 -1。

Q: 重复信任关系怎么处理？

A: 原题通常保证关系互不重复；若业务输入不保证，应以 (from,to) 为键用 Set 去重，否则重复边会虚增度数，导致错误识别。

来源：前端高频算法原题解析.pdf 的“找到小镇的法官”；与图基础中的邻接表、复杂度和输入校验方法融合整理。

相关专题：图基础知识速览、拓扑排序：课程表问题、图的 DFS 连通性。