Граф — это набор вершин и рёбер, каждое ребро соединяет две вершины. Вершины — это «объекты» (города, станции, клетки поля, состояния замка), рёбра — «можно перейти из одного в другое».
| Понятие | Что означает |
|---|---|
| Неориентированный граф | По ребру можно идти в обе стороны (дорога с двусторонним движением) |
| Ориентированный граф | Ребро можно пройти только от к (улица с односторонним движением) |
| Петля | Ребро из вершины в саму себя |
| Кратные рёбра | Несколько рёбер между одной и той же парой вершин |
| Степень вершины | Число рёбер, выходящих из вершины |
| Путь | Последовательность вершин, где соседние соединены ребром |
| Длина пути | Число рёбер в пути (пока у рёбер нет весов) |
| Расстояние | Длина кратчайшего пути от до |
В олимпиадных задачах обычно — число вершин, — число рёбер. Вершины нумеруются с 1, а в массивах Python удобно завести лишнюю ячейку с индексом 0 и не делать пересчёт номеров.
Главное умение — увидеть граф там, где его не назвали. Поле лабиринта, комбинации замка, числа, которые превращаются друг в друга операциями, — всё это графы: «вершина = состояние», «ребро = один ход».
Есть три основных способа.
1. Список рёбер — просто список пар (a, b). Удобно, когда рёбра нужно перебирать целиком (это пригодится позже).
2. Матрица смежности — таблица , где g[a][b] = 1, если ребро есть. Занимает памяти: при это ячеек — невозможно. Годится только для маленьких (до нескольких сотен).
3. Списки смежности — для каждой вершины список её соседей. Память . Это основной способ.
g = [[] for _ in range(n + 1)] # НЕ [[]] * (n + 1) - это n+1 ссылок на ОДИН список!
for _ in range(m):
a, b = ...
g[a].append(b)
g[b].append(a) # для неориентированного графа - в обе стороны
Ловушка Python. Запись
[[]] * (n + 1)создаёт ссылок на один и тот же список: добавив соседа одной вершине, вы добавите его всем. Всегда используйте генератор[[] for _ in range(n + 1)].
При входные данные содержат сотни тысяч чисел. Вызов input() на каждую строку работает в разы медленнее, чем нужно. Стандартный олимпиадный приём — прочитать весь вход одним вызовом и разбить на слова:
import sys
def main():
data = sys.stdin.buffer.read().split() # список байтовых строк: [b'6', b'7', b'1', ...]
n, m = int(data[0]), int(data[1])
p = 2 # указатель на следующее непрочитанное слово
for _ in range(m):
a = int(data[p]); b = int(data[p + 1]); p += 2
...
sys.stdout.write("\n".join(map(str, answer)) + "\n") # вывод одной операцией
main()
Почему это быстро:
sys.stdin.buffer.read() читает все байты за один системный вызов;split() без аргументов делит по любым пробельным символам, переводы строк не мешают;main() работает быстрее, чем на верхнем уровне: локальные переменные Python находит быстрее глобальных;print() медленнее одного sys.stdout.write; ответы копят в список и выводят через "\n".join(...).Строку из входа (например, строку лабиринта) удобно оставить байтовой: row[c] у байтовой строки — это число (код символа). Код '#' равен 35, '.' — 46. Сравнение чисел быстрее сравнения строк.
Задача: найти расстояния от вершины до всех вершин невзвешенного графа.
Идея: обходим граф «волнами». Сначала (расстояние 0), потом все её соседи (расстояние 1), потом их ещё не посещённые соседи (расстояние 2) и так далее. Чтобы вершины обрабатывались строго в порядке расстояний, используем очередь: кто раньше пришёл, тот раньше обработан.
from collections import deque
dist = [-1] * (n + 1) # -1 = "ещё не посещена"
dist[s] = 0
q = deque([s])
while q:
v = q.popleft()
for u in g[v]:
if dist[u] == -1: # отмечаем СРАЗУ при добавлении в очередь
dist[u] = dist[v] + 1
q.append(u)
Пошагово на графе с рёбрами 1–2, 1–3, 2–4, 3–4, 4–5 из вершины 1:
| Шаг | Достаём | Добавляем в очередь | Очередь после шага |
|---|---|---|---|
| 1 | 1 (dist 0) | 2, 3 (dist 1) | 2, 3 |
| 2 | 2 | 4 (dist 2) | 3, 4 |
| 3 | 3 | — (4 уже отмечена) | 4 |
| 4 | 4 | 5 (dist 3) | 5 |
| 5 | 5 | — | пусто |
Почему это правильно: в очереди в любой момент лежат вершины только с расстоянием и , причём сначала все . Значит, вершина впервые отмечается именно из ближайшего слоя.
Сложность: каждая вершина попадает в очередь один раз, каждое ребро просматривается один-два раза: .
Важные детали BFS в Python.
- Очередь — только
collections.deque. У спискаlist.pop(0)работает за , и BFS превращается в .- Отмечать вершину нужно при добавлении в очередь, а не при извлечении, иначе одна вершина попадёт в очередь много раз.
- Массив
distодновременно служит и массивом «посещена ли вершина»: отдельныйvisitedне нужен.
Чтобы вывести сам кратчайший путь, а не только длину, запоминаем, откуда пришли: parent[u] = v в момент, когда отмечаем . Потом идём от конца по parent до начала и разворачиваем список.
Есть и второй способ, удобный, когда путь нужно выбрать по дополнительному правилу. Запускаем BFS от конечной вершины . Тогда dist[v] — расстояние от до . Стоя в вершине , мы можем пойти в любого соседа с dist[u] == dist[v] - 1: каждый такой шаг приближает к ровно на 1, и путь остаётся кратчайшим. Среди подходящих соседей можно выбирать по любому правилу (например, наименьший номер) — выбор на каждом шаге независим и не ломает кратчайшесть.
Приём «BFS от конца». Если нужно выбрать среди всех кратчайших путей «лучший» по жадному правилу, считаем расстояния до цели и идём от старта, на каждом шаге выбирая лучший из соседей, которые на 1 ближе к цели.
Поле — граф, где вершины — свободные клетки, рёбра — соседние по стороне клетки. Списки смежности строить не нужно: соседей вычисляем на лету.
Приём 1. Одномерная нумерация. Клетку кодируем одним числом , где — ширина. Тогда соседи — это и . Один список вместо списка списков быстрее и экономнее по памяти.
Приём 2. Рамка из стен. Окружаем поле рамкой шириной в одну клетку и считаем её стенами. Поле становится размером , , а исходная клетка получает номер . Теперь не нужна проверка выхода за границы: шаг из крайней клетки упирается в стену рамки.
W = m + 2
free = bytearray((n + 2) * W) # 0 = стена (рамка тоже стена), 1 = свободно
for r in range(n):
row = data[2 + r] # байтовая строка, row[c] - код символа
for c in range(m):
if row[c] != 35: # 35 - код '#'
free[(r + 1) * W + c + 1] = 1
moves = (1, -1, W, -W)
...
for dv in moves:
u = v + dv
if free[u] and dist[u] == -1:
...
bytearray хранит один байт на клетку — в 8 раз компактнее списка ссылок.
Иногда расстояние нужно считать от ближайшего из нескольких стартов: «через сколько минут огонь дойдёт до клетки, если очагов несколько». Решение: положить в очередь сразу все источники с расстоянием 0 и запустить обычный BFS. Это то же самое, что добавить фиктивную вершину, соединённую со всеми источниками, и начать из неё.
Многоисточниковый BFS работает за — так же, как обычный. Запускать BFS из каждого источника отдельно — грубая ошибка: это в раз дольше.
Часто граф не задан во входе — его надо придумать. Пример: число , операции «умножить на 2» и «вычесть 1». Вершины — числа, рёбра — операции. BFS по такому графу находит минимальное число операций.
Правила работы с неявным графом:
dist — обычный список по индексу, а не словарь. Список в разы быстрее и компактнее словаря.(v // 10**i) % 10; степени десяти лучше заранее посчитать в список.В городе станций метро и перегонов. По каждому перегону поезда ходят в обе стороны, проезд по любому перегону занимает одинаковое время. Турист хочет попасть со станции на станцию , проехав как можно меньше перегонов.
Кратчайших маршрутов может быть несколько. Турист записывает маршрут как последовательность номеров станций и выбирает лексикографически наименьший из всех кратчайших маршрутов: сравниваются первые различающиеся номера станций.
Входные данные
В первой строке — числа и . В следующих строках — пары : станции, соединённые перегоном. Возможны петли и несколько перегонов между одной парой станций. В последней строке — числа и .
Выходные данные
Если добраться невозможно, выведите -1. Иначе в первой строке выведите число перегонов в кратчайшем маршруте, во второй — номера станций маршрута, начиная с и заканчивая .
Ограничения
, , .
Ограничение времени — 2 с, памяти — 256 МБ.
Пример 1
Ввод:
6 7
1 2
1 3
2 4
3 4
4 5
5 6
3 6
1 5
Вывод:
3
1 2 4 5
Пример 2
Ввод:
3 1
1 2
1 3
Вывод:
-1
Пояснение к примеру 1. Кратчайших маршрутов три: 1 2 4 5, 1 3 4 5 и 1 3 6 5. Лексикографически наименьший — первый.
Подсказки
- Не пытайтесь перебирать все кратчайшие маршруты — их может быть экспоненциально много.
- Если для каждой станции известно расстояние до , то на каждом шаге легко понять, какие соседи «ведут правильно».
- Подумайте, зачем жадно брать наименьший номер именно на первом шаге, затем на втором и так далее, и почему такой выбор не может «загнать в тупик».
Иван находится в лабиринте размером . Клетка # — стена, . — свободная клетка, S — клетка Ивана, F — очаг пожара (очагов может быть несколько или ни одного).
Каждую минуту одновременно происходит следующее:
Иван не может войти в клетку, которая загорается в ту же минуту, когда он туда приходит, или горела раньше. Стоя в клетке на краю лабиринта, Иван за одну минуту выходит наружу.
Найдите минимальное время, за которое Иван выйдет из лабиринта.
Входные данные
В первой строке — числа и . Далее строк по символов из набора #, ., S, F. Символ S встречается ровно один раз.
Выходные данные
Одно число — минимальное время выхода в минутах — или слово IMPOSSIBLE, если выйти нельзя.
Ограничения
.
Ограничение времени — 2 с, памяти — 256 МБ.
Пример 1
Ввод:
6 6
######
#S...#
#.##.#
#.#.F#
#....#
#.####
Вывод:
5
Пример 2
Ввод:
6 6
######
#S...#
#.##.#
#.#F.#
#....#
#.####
Вывод:
IMPOSSIBLE
Пояснение. В первом примере Иван спускается по левому коридору и приходит в нижнюю клетку выхода через 4 минуты, а огонь — только через 5. Пятая минута уходит на выход наружу. Во втором примере очаг на одну клетку ближе: огонь доходит до клетки над выходным коридором в ту же минуту, что и Иван, и путь к выходу перекрыт.
Подсказки
- Для любой клетки можно заранее узнать момент, когда туда придёт огонь. Сколько при этом нужно запусков BFS для огня?
- Когда моменты возгорания известны, Иван ищет кратчайший путь в графе, где в клетку можно войти, только если он приходит туда строго раньше огня.
- Чтобы не проверять выход за границы на каждом шаге, окружите поле рамкой.
Кодовый замок состоит из колёсиков, на каждом цифры от 0 до 9 по кругу. За один ход можно повернуть одно колёсико на одну позицию вперёд или назад; после 9 идёт 0, перед 0 — 9.
Сейчас на замке комбинация , открывает его комбинация . Есть запретных комбинаций: если на замке оказывается запретная комбинация, он блокируется навсегда. Найдите минимальное число ходов, за которое можно открыть замок, ни разу не оказавшись в запретной комбинации.
Входные данные
В первой строке — число . Во второй — комбинации и , каждая ровно из цифр (возможны ведущие нули). В третьей — число . Далее строк по одной запретной комбинации из цифр. Запретные комбинации могут совпадать с или .
Выходные данные
Минимальное число ходов или -1, если открыть замок невозможно.
Ограничения
, .
Ограничение времени — 2 с, памяти — 256 МБ.
Пример 1
Ввод:
4
0000 0202
5
0201
0101
0102
1212
2002
Вывод:
6
Пример 2
Ввод:
2
00 55
0
Вывод:
10
Пример 3
Ввод:
1
3 7
1
7
Вывод:
-1
Подсказки
- Сколько всего комбинаций у замка при и сколько ходов возможно из каждой?
- Комбинацию удобно хранить как обычное целое число от до . Как изменится это число при повороте -го колёсика вперёд, если на нём не 9? А если 9?
- Разберите отдельно случай, когда запрещены сами или .