Первая олимпиада Олмат.Программирование. 23.02.26

Тема: Спутниковые сети Уровень: Профи

📜 Третья находка

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

📌 Спутники

В реальных спутниковых группировках аппараты образуют распределённую сеть межспутниковой связи (Inter-Satellite Links, ISL).
Каждый спутник выступает не только источником данных, но и ретранслятором, передающим информацию соседям.

Такая архитектура позволяет:

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

Однако в космосе каналы связи могут выходить из строя:

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

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

С инженерной точки зрения это означает потерю глобальной маршрутизации и снижение отказоустойчивости всей орбитальной системы.

⚙️ Как это работает ?

В реальных спутниковых системах постоянно выполняется мониторинг топологии сети.
Наземные центры управления анализируют:

• какие спутники видят друг друга,
• какие каналы активны,
• какие участки сети изолированы.

Это необходимо для:

• планирования новых каналов связи,
• перераспределения частот и лазерных линий,
• корректировки орбит,
• перенастройки маршрутизации,
• ввода резервных аппаратов.

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

На практике это может означать:

• включение резервных лазерных терминалов,
• изменение направленности антенн,
• вывод дополнительного спутника-ретранслятора,
• программную перенастройку маршрутов.

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

📌 Задача

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

📥 Формат входных данных

В первой строке заданы два целых числа n и m — количество спутников и количество работающих каналов связи.
Далее в m строках заданы пары целых чисел u и v — номера спутников, между которыми существует двусторонний канал связи.

Ограничения

• 1 ≤ n ≤ 200000
• 0 ≤ m ≤ 200000
• 1 ≤ u, v ≤ n
• Граф неориентированный
• Возможны повторяющиеся рёбра (их можно игнорировать)
• Возможны петли u = v (они не влияют на связность)

📤 Формат выходных данных

Выведи одно целое число — минимальное количество новых соединений, необходимых для восстановления полной связности спутниковой сети.

📘 Примеры

Пример 1

Входные данные:

4 2  
1 2  
3 4

Выходные данные:
1

Пример 2

Входные данные:

5 4  
1 2  
2 3  
3 4  
4 5

Выходные данные:
0

Пример 3

Входные данные:

6 1  
2 5

Выходные данные:
4