Разбор задачи «Центральный фонарь»

Идея задачи

Нам дано n кварталов и m запрещённых пар. Для каждой запрещённой пары нельзя строить прямую дорожку между этими двумя кварталами.

Нужно построить минимальное количество дорожек так, чтобы:

• ни одна дорожка не соединяла запрещённую пару;
• из любого квартала можно было добраться до любого другого не более чем по двум дорожкам.

Гарантируется, что ответ существует.

Главная цель задачи — заметить очень удобную конструкцию: звезду.

Если выбрать один центральный квартал и соединить его со всеми остальными, то:

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

Значит, такая конструкция сразу удовлетворяет требованию про путь не длиннее двух дорожек.

Остаётся понять, как выбрать центр так, чтобы все дороги от него были разрешены.

Ключевое наблюдение

Посмотрим на все запрещённые пары.

Если некоторый квартал встречается в запрещённой паре, пометим его как «плохой». Тогда квартал, который не встречается ни в одной запрещённой паре, можно безопасно выбрать центром.

Почему?

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

По условию ответ существует, а значит, такой квартал обязательно найдётся.

Почему количество дорожек минимально

Любой связный граф на n вершинах содержит как минимум n - 1 ребро.

Мы строим именно n - 1 дорожек: соединяем центр со всеми остальными кварталами.

Значит:

• меньше сделать нельзя;
• наша конструкция минимальна.

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

1. Считываем n и m.
2. Создаём массив bad, где bad[v] = True, если квартал v встречался хотя бы в одной запрещённой паре.
3. Читаем все m пар и помечаем их концы.
4. Находим любой квартал center, для которого bad[center] = False.
5. Выводим n - 1.
6. Для всех кварталов v != center выводим дорожку center v.

Разбор на примере

Пусть вход такой:

4 2
1 2
2 3

Запрещённые пары:

• 1 2
• 2 3

Тогда кварталы 1, 2, 3 встречаются в запрещённых парах, а квартал 4 — нет.

Значит, выбираем 4 как центр и строим дороги:

• 4 1
• 4 2
• 4 3

Теперь:

• из 4 в любой квартал путь длины 1;
• между 1 и 2 можно пройти как 1 -> 4 -> 2;
• между 1 и 3 можно пройти как 1 -> 4 -> 3;
• между 2 и 3 можно пройти как 2 -> 4 -> 3.

Все пути имеют длину не более 2.

Почему решение корректно

Докажем это строго.

1. Все выведенные дорожки разрешены

Мы выбираем квартал center, который не встречается ни в одной запрещённой паре.

Значит, пара (center, v) не запрещена ни для одного квартала v. Следовательно, каждую выведенную дорожку строить можно.

2. Между любыми двумя кварталами есть путь длины не более 2

• Если один из кварталов — это center, то путь состоит из одной дорожки.
• Если оба квартала не равны center, то можно пройти через центр: сначала в center, потом в нужный квартал. Это путь длины 2.

Значит, условие задачи выполнено.

3. Количество дорожек минимально

Любой граф, в котором из каждой вершины достижимы все остальные, должен быть связным. У любого связного графа на n вершинах не меньше n - 1 рёбер.

Мы выводим ровно n - 1 дорожек. Следовательно, это минимально возможное число.

Итак, алгоритм корректен.

Сложность алгоритма

Мы один раз читаем входные данные и один раз проходим по вершинам.

По времени

O(n + m)

По памяти

O(n)

Эталонное решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<bool> bad(n + 1, false);

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

    int center = -1;
    for (int v = 1; v <= n; ++v) {
        if (!bad[v]) {
            center = v;
            break;
        }
    }

    cout << n - 1 << '\n';
    for (int v = 1; v <= n; ++v) {
        if (v != center) {
            cout << center << ' ' << v << '\n';
        }
    }

    return 0;
}

Решение на Python

import sys


def solve():
    input = sys.stdin.readline

    n, m = map(int, input().split())
    bad = [False] * (n + 1)

    for _ in range(m):
        a, b = map(int, input().split())
        bad[a] = True
        bad[b] = True

    center = -1
    for v in range(1, n + 1):
        if not bad[v]:
            center = v
            break

    print(n - 1)
    for v in range(1, n + 1):
        if v != center:
            print(center, v)


if __name__ == "__main__":
    solve()

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

1. Пытаться строить что-то сложнее звезды

Иногда хочется придумывать общий граф, проверять расстояния, запускать BFS и так далее. В этой задаче это не нужно. Здесь важно заметить красивую конструкцию из звезды.

2. Искать вершину, которая не запрещена только с некоторыми кварталами

Нам нужен квартал, который вообще не встречался во входных данных. Именно тогда он гарантированно подходит как центр.

3. Забыть, что нужен минимум по числу дорожек

Можно построить много разных подходящих графов, но задача требует минимальное число дорожек. Связный граф меньше чем с n - 1 рёбрами невозможен.

4. Ошибка с индексацией

Вершины нумеруются с 1 до n, значит, массив удобнее делать размера n + 1.

Что полезно вынести из этой задачи

Эта задача хорошо тренирует важную мысль: иногда не нужно строить «любой правильный граф», а нужно заметить самую простую конструкцию, которая автоматически выполняет все требования.

Здесь такой конструкцией является звезда:

• она даёт расстояние не больше 2;
• использует минимальное число рёбер;
• строится очень просто после правильного выбора центра.

Именно такие идеи часто встречаются в задачах на конструктивные алгоритмы.