Разбор задачи «Космическая станция»

Идея задачи

Нам дан неориентированный граф, который гарантированно является звездой.

Это значит, что:

• существует ровно одна центральная вершина;
• она соединена со всеми остальными;
• любая другая вершина соединена только с центром.

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

Нужно определить номер этого главного модуля.

Главное наблюдение

Рассмотрим первые два ребра:

• первое ребро соединяет вершины a и b;
• второе ребро соединяет вершины c и d.

Так как граф — звезда, центральная вершина входит в каждое ребро.

Значит, среди первых двух рёбер обязательно есть общая вершина. Именно она и является центром.

Например:

• 1 2
• 2 3

Общая вершина — 2, значит она и есть центр.

Из этого сразу получается очень короткое решение:

• если a встречается во втором ребре, то ответ a;
• иначе ответ b.

Почему этого достаточно

В задаче гарантируется, что входные данные уже образуют звезду.

Поэтому нам не нужно:

• строить список смежности;
• считать степени всех вершин;
• проверять корректность графа.

Достаточно использовать свойство звезды.

У любой звезды:

• центр встречается во всех рёбрах;
• нецентральная вершина встречается ровно в одном ребре.

Значит, у первых двух рёбер общая вершина может быть только одна, и это обязательно центр.

Алгоритм

1. Считываем n.
2. Считываем первые два ребра.
3. Проверяем, входит ли первая вершина первого ребра во второе ребро.
4. Если да — выводим её.
5. Иначе выводим вторую вершину первого ребра.

Обратите внимание: остальные рёбра нам уже не нужны.

Пошаговый разбор на примере

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

4
1 2
2 3
4 2

Первые два ребра:

• (1, 2)
• (2, 3)

Проверяем вершину 1:

• во втором ребре её нет.

Значит, центр — это вторая вершина первого ребра, то есть 2.

Ответ:

2

Доказательство корректности

Докажем, что алгоритм всегда выводит правильный ответ.

Пусть первые два ребра имеют вид:

• (a, b)
• (c, d).

Так как граф является звездой, существует центральная вершина x, соединённая со всеми остальными вершинами. Тогда каждое ребро графа содержит вершину x.

Значит:

• среди вершин первого ребра одна из вершин равна x;
• среди вершин второго ребра одна из вершин тоже равна x.

Следовательно, у первых двух рёбер есть общая вершина, и эта общая вершина — центр графа.

Алгоритм сначала проверяет, равна ли вершина a одной из вершин второго ребра.

• Если да, то a и есть общая вершина, значит это центр.
• Если нет, то общей вершиной должна быть b, значит центр — b.

Итак, алгоритм всегда находит и выводит центральную вершину звезды.

Что и требовалось доказать.

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

Алгоритм использует только первые два ребра.

• Время: O(1)
• Память: O(1)

Это оптимальное решение.

Реализация на C++

#include <iostream>
using namespace std;

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

    int a, b, c, d;
    cin >> a >> b;
    cin >> c >> d;

    if (a == c || a == d) {
        cout << a << '\n';
    } else {
        cout << b << '\n';
    }

    return 0;
}

Реализация на Python

n = int(input())
a, b = map(int, input().split())
c, d = map(int, input().split())

if a == c or a == d:
    print(a)
else:
    print(b)

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

Ошибка 1. Пытаться считать степени всех вершин

Такое решение тоже будет работать, но оно сложнее, чем нужно.

Раз в условии гарантируется, что граф — звезда, можно использовать более простое свойство: центр находится по первым двум рёбрам.

Ошибка 2. Считывать все рёбра в массив без необходимости

Для этой задачи это не нужно. Достаточно только двух первых рёбер.

Ошибка 3. Путать условие с произвольным деревом

Здесь дан не просто связный граф и не просто дерево, а именно звезда. Это очень сильное ограничение, и именно оно позволяет решить задачу за константное время.

Вывод

Ключ к задаче — заметить простое свойство звезды:

центральная вершина содержится в каждом ребре.

Поэтому достаточно посмотреть только на первые два ребра и найти их общую вершину.

Это делает решение очень коротким, быстрым и аккуратным.