Find the Town Judge

В городе из n жителей (пронумерованы от 1 до n) может быть судья (town judge), если он существует и удовлетворяет двум условиям: (1) судья никому не доверяет; (2) все остальные n-1 жителей доверяют судье. Дан массив пар `trust`, где `trust[i] = [a, b]` значит "житель a доверяет жителю b". Нужно вернуть номер судьи, если он существует и однозначно определён, иначе -1.In a town of n people (numbered 1 to n), there may be a town judge if they exist and satisfy two properties: (1) the judge trusts nobody; (2) everybody else (all n-1 other people) trusts the judge. Given an array of pairs `trust`, where `trust[i] = [a, b]` means "person a trusts person b," return the judge's label if they exist and are uniquely identifiable, otherwise -1.

// Example 1
n = 2, trust = [[1,2]]
// output: 2  (1 доверяет 2; 2 никому не доверяет → судья)(1 trusts 2; 2 trusts nobody → the judge)

// Example 2
n = 3, trust = [[1,3],[2,3]]
// output: 3  (и 1, и 2 доверяют 3; 3 никому не доверяет → судья)(both 1 and 2 trust 3; 3 trusts nobody → the judge)

// Example 3
n = 3, trust = [[1,3],[2,3],[3,1]]
// output: -1  (3 сам кому-то доверяет → не может быть судьёй)(3 trusts someone themselves → can't be the judge)

Первый шаг — увидеть граф там, где условие говорит "доверие". `trust[i] = [a, b]` — это ровно ориентированное ребро a→b из терминологии 3.1.1. Массив `trust` целиком — это ни что иное, как список рёбер (edge list) ориентированного графа на n вершинах — самое сырое представление, из которого 3.1.1 показывал, как строить матрицу смежности или список смежности.The first step is seeing a graph where the statement says "trust." `trust[i] = [a, b]` is exactly a directed edge a→b in 3.1.1's terminology. The whole `trust` array is nothing but the edge list of a directed graph on n vertices — the rawest representation, from which 3.1.1 showed how to build an adjacency matrix or adjacency list.

Второй шаг — перевести условие задачи на язык терминов из 3.1.1. "b доверяют все остальные n-1 жителей" значит in-degree(b) = n-1 (в b входит ребро от каждой другой вершины). "Судья никому не доверяет" значит out-degree(b) = 0 (из b не выходит ни одного ребра). Задача "найти судью" — это буквально "найти вершину с in-degree = n-1 и out-degree = 0" — вершину, которая формулировкой напоминает "сток" (все пути ведут в неё, из неё — никуда).The second step is translating the problem statement into 3.1.1's terms. "Everyone else — all n-1 people — trusts b" means in-degree(b) = n-1 (an edge comes into b from every other vertex). "The judge trusts nobody" means out-degree(b) = 0 (no edge leaves b). "Find the judge" is literally "find a vertex with in-degree = n-1 and out-degree = 0" — a vertex resembling a "sink," in the sense that every path leads into it and none leave.

Третий шаг — заметить, что "разница между входящими и исходящими" — это ровно то, что нужно посчитать, и её можно посчитать одним проходом по списку рёбер, без построения полноценной матрицы или списка смежности из 3.1.1: заведём массив `score` размера n+1 (нумерация с 1), и для каждого ребра a→b сделаем `score[a]--` (a кому-то доверяет — это "минус" для его шанса быть судьёй) и `score[b]++` (b получил доверие — "плюс" для его шанса). У настоящего судьи в конце `score[judge] == n - 1`, потому что n-1 плюсов пришло от всех остальных и ни одного минуса не было (иначе он сам кому-то доверял бы).The third step is noticing that "the difference between incoming and outgoing" is exactly what needs counting, and it can be counted in a single pass over the edge list, with no need to build a full matrix or adjacency list from 3.1.1: keep a `score` array of size n+1 (1-indexed), and for each edge a→b do `score[a]--` (a trusts someone — a "minus" against a's chance of being the judge) and `score[b]++` (b received trust — a "plus" for b's chance). The real judge ends up with `score[judge] == n - 1`, because n-1 pluses arrived from everyone else and there were zero minuses (otherwise they'd trust someone themselves).

class Solution {
public:
    int findJudge(int n, std::vector<std::vector<int>>& trust) {
        std::vector<int> score(n + 1, 0);  // score[v] = in-degree(v) - out-degree(v)// score[v] = in-degree(v) - out-degree(v)

        for (const auto& edge : trust) {
            int a = edge[0], b = edge[1];
            score[a]--;   // a доверяет b → минус a, плюс b// a trusts b → minus a, plus b
            score[b]++;
        }

        for (int person = 1; person <= n; ++person) {
            if (score[person] == n - 1) return person;  // нашли судью// found the judge
        }
        return -1;  // судьи нет// no judge exists
    }
};

Сложность: O(V + E) по времени (V = n для инициализации `score`, E = trust.size() для одного прохода по рёбрам, плюс ещё O(V) для финального поиска) и O(V) по памяти — то есть ровно та же асимптотика, что 3.1.1 даёт для списка смежности, хотя мы явный список смежности даже не строили. Это и есть суть задачи: понять, что полное представление графа избыточно, если нужен только один агрегат (степень вершины) — почти как в примере 05 из 3.1.1 про степень вершины для топологической сортировки.Complexity: O(V + E) time (V = n for initializing `score`, E = trust.size() for one pass over the edges, plus O(V) for the final search) and O(V) memory — exactly the same asymptotic that 3.1.1 gives for an adjacency list, even though we never built an explicit adjacency list. That's the point of the problem: recognizing that a full graph representation is overkill when only one aggregate (vertex degree) is actually needed — much like the degree-counting example in 3.1.1 for topological sort.

• LeetCode 997 — Find the Town Judge