Разбор задачи «Судья часового квартала»

Идея задачи

Есть n жителей. Для некоторых пар известно, что житель a доверяет жителю b.

Нужно найти такого жителя, который одновременно:

• никому не доверяет;
• получает доверие от всех остальных.

Если такой житель существует, нужно вывести его номер. Иначе вывести -1.

По сути, нам нужно проверить для каждого человека два значения:

• скольким людям доверяет он сам;
• сколько людей доверяют ему.

Как удобно мыслить про задачу

Представим, что каждый житель — это вершина графа.

Если a доверяет b, то проведём ориентированное ребро a -> b.

Тогда условие на судью выглядит так:

• из вершины судьи не выходит ни одного ребра;
• в вершину судьи входит ровно n - 1 ребро.

Значит, достаточно для каждого человека хранить:

• out[i] — сколько исходящих рёбер у вершины i, то есть скольким людям доверяет человек i;
• in[i] — сколько входящих рёбер у вершины i, то есть сколько людей доверяют человеку i.

После этого остаётся пройти по всем жителям и найти такого, у кого:

• out[i] == 0
• in[i] == n - 1

Если такой человек найден, это и есть ответ.

Пошаговый алгоритм

1. Считываем n и m.

2. Создаём два массива размера n + 1:

   • in
   • out

3. Для каждой пары a b:

   • увеличиваем out[a]
   • увеличиваем in[b]

4. Проверяем всех жителей от 1 до n:

   • если out[i] == 0 и in[i] == n - 1, выводим i
5. Если никто не подошёл, выводим -1

Почему это работает

Докажем корректность.

Если житель i является судьёй, то по условию:

• он никому не доверяет, значит out[i] = 0;
• все остальные доверяют ему, значит in[i] = n - 1.

То есть настоящий судья обязательно будет найден нашим алгоритмом.

Теперь наоборот. Если для жителя i выполнено:

• out[i] = 0
• in[i] = n - 1

это означает, что он никому не доверяет, а все остальные доверяют ему. Значит, он точно удовлетворяет определению судьи.

Следовательно, алгоритм находит ответ тогда и только тогда, когда судья существует.

Оценка сложности

Пусть m — количество записей о доверии.

Мы:

• один раз обрабатываем все m пар;
• один раз проходим по всем n жителям.

Итог:

• Время: O(n + m)
• Память: O(n)

Это быстро и подходит для заданных ограничений.

Разберём пример

Пусть дан ввод:

4 3
1 4
2 4
3 4

Тогда:

• человек 1 доверяет 4
• человек 2 доверяет 4
• человек 3 доверяет 4

Посчитаем массивы:

• out[1] = 1, out[2] = 1, out[3] = 1, out[4] = 0
• in[1] = 0, in[2] = 0, in[3] = 0, in[4] = 3

Так как n = 4, для судьи нужно:

• out[i] = 0
• in[i] = 3

Этому условию подходит житель 4, значит ответ — 4.

Решение на C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> in(n + 1, 0), out(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        out[a]++;
        in[b]++;
    }

    for (int i = 1; i <= n; i++) {
        if (out[i] == 0 && in[i] == n - 1) {
            cout << i << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

Пояснение к коду на C++

Сначала создаются два массива:

• in — сколько человек доверяют каждому жителю;
• out — скольким доверяет каждый житель.

Дальше каждая строка a b означает, что:

• у a увеличивается число исходящих связей;
• у b увеличивается число входящих связей.

После обработки всех пар остаётся только найти жителя, для которого одновременно выполнены два условия судьи.

Решение на Python

n, m = map(int, input().split())

incoming = [0] * (n + 1)
outgoing = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    outgoing[a] += 1
    incoming[b] += 1

for i in range(1, n + 1):
    if outgoing[i] == 0 and incoming[i] == n - 1:
        print(i)
        break
else:
    print(-1)

Пояснение к коду на Python

Идея полностью такая же, как и в решении на C++.

• outgoing[i] показывает, скольким людям доверяет житель i;
• incoming[i] показывает, сколько людей доверяют жителю i.

Затем мы перебираем всех жителей и ищем того, кто никому не доверяет и кому доверяют все остальные.

Конструкция for ... else в Python означает, что блок else выполнится только тогда, когда цикл завершился без break.

То есть:

• если подходящий житель найден, программа печатает его номер и выходит из цикла;
• если не найден никто, программа печатает -1.

Частые ошибки

1. Перепутать входящую и исходящую степень

Если a доверяет b, то:

• out[a] увеличивается;
• in[b] увеличивается.

Именно в таком порядке.

2. Использовать нумерацию с нуля

По условию жители нумеруются от 1 до n, поэтому удобнее сразу завести массивы размера n + 1 и работать с индексами от 1.

3. Забыть случай n = 1

Если в городе всего один житель и записей о доверии нет, то он подходит под условие:

• никому не доверяет;
• все остальные жители доверяют ему.

Так как остальных жителей нет, условие про доверие выполняется автоматически. Ответом будет 1.

4. Пытаться проверять каждого жителя полным перебором

Можно было бы для каждого человека отдельно смотреть все пары доверия, но это дало бы более медленное решение. Гораздо лучше сразу посчитать нужные значения для всех.

Вывод

Главная идея задачи — перевести условие в язык графов:

• судья никому не доверяет → исходящая степень равна 0;
• все доверяют судье → входящая степень равна n - 1.

После этого задача решается очень прямо: считаем для каждого жителя количество входящих и исходящих рёбер, а затем ищем подходящего кандидата.

Это типичная задача на аккуратную работу с графовой моделью и подсчётами по массивам.