Алгоритм распространения "эпидемии" в графе

Автор: Гудков Денис Андреевич Задача №2

Компиляция и запуск

C++ версия

# Компиляция с оптимизацией
g++ -O2 -o plague plague.cpp

# Запуск
./plague

# Запуск с тестовыми данными
echo "3
1 2
2 3
3 1" | ./plague

Пример входных данных

3                    # количество рёбер
1 2                  # ребро
1 3
2 3               

Пример выходных данных

2                    # количество изначально заражённых вершин
2, 3    # список заражённых вершин

Проектные решения

1. Алгоритм решения

• Города-вершины графа со степенью не больше 1 считаются заражёнными сразу, так как иначе они сами не могут заразиться от соседей. После этого выполняется распространение инфекции с помощью функции spread(...). Далее в цикле, в котором максимум 500 итераций, заражается вершина с наибольшей степенью, выполняется распространение. Если все города заразились, то цикл прекращается.
• Если получилось не больше 1000 зараженных городов, то алгоритм пытается удалить лишние: каждый зараженный город v временно исключает из множества, запускает распространение заново. Если все города всё ещё заражаются — город v удаляется из результата.

4. Временная сложность

• Построение графа: O(V log V + E)
• Распространение: O(V + E) на итерацию
• Общая сложность: O(k × (V + E)) где k ≤ 500
• Оптимизация: O(V²) только для малых наборов

5. Сложность по памяти

• O(V + E) для хранения графа и вспомогательных структур
• O(V) для массивов состояния

Файлы проекта

• plague.cpp - основная C++ реализация