Хранить граф в виде словаря множеств или взвешенный граф в виде словаря словарей достаточно удобно и прямолинейно.
Но, увы, не так быстро, как иногда требуется.
Во всех таких случаях нужно использовать просто списки или вектора (в C++).
Реальные данные обычно не являются последовательными числами (или просто целыми числами из не слишком большого диапазона),
поэтому сначала потребуется пронумеровать вершины по порядку, после чего уже решать задачу для последовательных целых чисел.
В этом листке всюду этот шаг мы пропустим.
Да и в спортивном программировании вообще обычно сразу начинают с чисел.
Итак, путь у нас зафиксировано число $N$, и гарантируется, что вершины — это числа от 1 до $N$.
Тогда обычный граф удобно хранить в виде списка смежности (по факту это — вектор векторов или список списков):
под индексом $i$ лежит список/вектор индексов соседей элемента $i$.
Если граф неориентированный, то храним оба ребра.
Если граф взвешенный, то есть рёбрам приписаны веса, то будем хранить массив пар индекс-вес_ребра.
Создание пустого графа и добавление рёбер:
# Обычный
adj = [[] for __ in range(N+1)]
adj[1].append(2)
adj[2].append(3)
# Взвешенный
adj = [[] for __ in range(N+1)]
adj[1].append([2, 17])
adj[2].append([3, -99])
from collections import deque
INF = float('inf')
distance = [INF] * (N+1)
distance[s] = 0
q = deque([s])
while q:
s = q.popleft()
for neighbor in adj[s]:
if distance[neighbor] != INF:
continue
distance[neighbor] = distance[s] + 1;
q.append(neighbor);
#define INF 2147483647
vector<int> distance;
distance.assign(N+1, INF);
distance[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int s = q.front(); q.pop();
for (auto neighbor : adj[s]) {
if (distance[neighbor] <> INF) continue;
distance[neighbor] = distance[s] + 1;
q.push(neighbor);
}
}
Соглашение о порядке обхода и формате задания графа
При обходе графа обычно существует достаточно большой произвол в порядке выбора начальных элементов, соседей и т.п.
Однако в этом листке для упрощения проверки при наличии любого произвольного выбора элементов необходимо начинать с наименьшего
(напоминаю, у нас все вершины — числа). Сложность необходимой для этого сортировки в сложности алгоритмов не учитывается.
Почти каждый граф в этом листке имеет вершины $1, 2, \ldots, N$ и $0 \leqslant M \leqslant \frac{N(N-1)}{2}$ рёбер.
Соответственно в первой строке даются числа $N$ и $M$.
Затем идут $M$ строчек с рёбрами, в каждой из которых указаны начальная вершина ребра, конечная вершина и, может быть, вес ребра.
Обход в глубину
A: Компоненты связности
Дан неориентированный граф. Необходимо посчитать количество его компонент связности и вывести их.
Во входном файле записано два числа $N$ и $M~(0 < N\leqslant 100000, 0\leqslant M\leqslant100000)$. В следующих $M$ строках записаны по два числа $i$ и $j~(1\leqslant i,j\leqslant N)$, которые означают, что вершины $i$ и $j$ соединены ребром.
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй — сами вершины в произвольном порядке.
6 4
3 1
1 2
5 4
2 3
3
3
1 2 3
2
4 5
1
6
Лес поиска в глубину, метки времени и типы рёбер
Лес поиска в глубину
Возьмём неоринтированный или ориентированный граф.
Пометим все вершины как непосещённые.
Выполним обход в глубину начиная с какой-нибудь непосещённой вершины.
Рассмотрим множество рёбер, после прохода по которым мы попадали в новую вершину.
Они образуют корневое дерево.
Пока остались непосещённые вершины, будем и дальше выбирать непосещённую вершину и делать обход в глубину.
Множество получившихся деревьев называется лесом поиска в глубину (DFS forest).
Добавим в граф виртуальную вершину $-1$,
а также по виртуальному ребру из $-1$ в корень каждого получившегося дерева.
Можно представлять себе получившийся обход как обход в глубину этого нового графа начиная с «виртуального корня».
Классиификация рёбер
Во время обхода в глубину ориентированного графа возникают рёбра 4-х типов:
Прямые рёбра (forward edges) ведут от вершины к её потомку, не являющемуся при этом её ребёнком.
Обратные рёбра (back edges) ведут от вершины к её предку.
Перекрёстные рёбра (cross edges) ведут от вершины к другой вершине, не являющейся ни предком, ни потомком первой (такая вершина уже полностью обработана в момент обнаружения перекрёстного ребра).
Метки времени
Метки времени — приём, который лежит в основе многих применений поиска в глубину.
Метки времени — это натуральные числа от \(1\) до \(2|V|\).
Каждая вершина при обходе в глубину получает две метки: время начала обработки и время окончания,
причём все метки всех вершин различны.
Заведём счётчик времени.
Изначально счётчик равен нулю.
Каждый раз, когда мы переходим от одной вершины к другой мы прибавляем к счётчику единицу.
Время начала обработки — это значение счётчика в тот момент, когда мы впервые пришли в рассматриваемую вершину.
Время окончания — это значение счётчика после того, как будет выполнен обход в глубину для всех сыновьих вершин.
Каждый раз, когда мы начинаем обход для какой-либо вершины, мы прибавляем 1 к счётчику.
Аналогично мы прибавляем 1 к счётчику после того, как закончили обход для данной вершины.
B: Лес поиска в глубину
Дан ориентированный граф.
Выведите предка каждой вершины в лесе обхода в глубину.
Для корней деревьев нужно вывести в качестве предка $-1$.
Сложность получившегося алгоритма должна быть $O(|V| + |E|)$.
Обратите внимание: для упрощения тестирования посещать вершины нужно в порядке их
возрастания, поэтому потребуется сортировка вершин в списках смежности. Сложность этой сортировки не нужно учитывать.
Дан ориентированный граф.
Для каждой вершины выведите метки времени при обходе в глубину.
Обратите внимание: для упрощения тестирования посещать вершины нужно в порядке их
возрастания, поэтому потребуется сортировка вершин в списках смежности. Сложность этой сортировки не нужно учитывать.
Дан ориентированный граф без циклов.
Необходимо вывести все его вершины в таком порядке,
чтобы из любой вершины с большим номером не существовало пути ни в какую вершину с меньшим номером.
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\) или \(O(\log(|V|)\cdot(|V| + |E|))\).
7 8
1 2
2 3
2 4
2 5
3 5
4 5
5 6
7 2
7 1 2 4 3 5 6
E: Классификация рёбер при поиске в глубину
При постоении леса обхода в глубину имеется 4 типа рёбер:
Прямые рёбра (forward edges) ведут от вершины к её потомку, не являющемуся при этом её ребёнком.
Обратные рёбра (back edges) ведут от вершины к её предку.
Перекрёстные рёбра (cross edges) ведут от вершины к другой вершине, не являющейся ни предком, ни потомком первой (такая вершина уже полностью обработана в момент обнаружения перекрёстного ребра).
Дан граф.
Выведите тип каждого ребра при построении леса обхода в глубину.
Рёбра необходимо выводить именно в том порядке, в котором они даются в условиях.
4 6
1 2
1 4
2 3
2 4
3 1
4 3
1 2 tree
1 4 forward
2 3 tree
2 4 tree
3 1 back
4 3 cross
Обход в ширину
F: Кратчайший путь в 0-1-графе
Имеется схема городского транспорта (неориентированный граф), в котором участвую автобусы и троллейбусы.
Проезд на автобусе стоит 1$, проезд на троллейбусе бесплатен.
Необходимо найти какой-нибудь самый дешёвый способ добраться от одной остановки до другой.
Если такого пути нет, то выведите -1.
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\).
Дан ориентированный граф.
Необходимо вывести любой из кратчайших циклов.
Если ни одного цикла нет, то выведите -1.
Сложность получившегося алгоритма должна быть \(O(|V|\cdot(|V| + |E|))\).
6 7
1 2
2 3
3 4
4 5
2 6
6 5
5 1
1 2 6 5 1
H: Кратчайший чётный путь
Дан ориентированный граф и несколько пар его вершин.
Выведите кратчайший путь чётной длины от одной вершины до другой, или -1, если такого пути нет.
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\).
5 6
1 5
1 2
2 4
2 3
3 4
4 5
2
1 5
3 2
1 2 3 4 5
-1
Эйлеров путь
I: Поиск эйлерова пути
В городе есть $N$ площадей, соединённых улицами. При этом количество улиц не превышает $100000$ и существует не более трёх площадей, на которые выходит нечётное количество улиц. Для каждой улицы известна её длина. По каждой улице разрешено движение в обе стороны. В городе есть хотя бы одна улица. От каждой площади до любой другой можно дойти по улицам.
Почтальону требуется пройти хотя бы один раз по каждой улице. Почтальон хочет, чтобы длина его пути была минимальна. Он может начать движение на любой площади и закончить также на любой (в том числе и на начальной).
Помогите почтальону составить такой маршрут.
Сначала записано число $N$ — количество площадей в городе $(2\leqslant N\leqslant1000)$. Далее следуют $N$ строк, задающих улицы. В $i$-ой из этих строк находится число $m_i$ — количество улиц, выходящих из площади $i$. Далее следуют $m_i$ пар натуральных чисел: в $j$-ой паре первое число — номер площади, в которую идет $j$-ая улица с $i$-ой площади, а второе число — длина этой улицы.
Между двумя площадями может быть несколько улиц, но не может быть улицы с площади на нее саму.
Все числа во входном файле не превосходят $100000$.
Если решение существует, то в первую строку выходного файла выведите одно число — количество улиц в искомом маршруте, а во вторую — номера площадей в порядке их посещения.
Если решения нет, выведите в выходной файл одно число $-1$.
Если решений несколько, выведите любое.
4
2 2 1 2 2
4 1 2 4 4 3 5 1 1
2 2 5 4 8
2 3 8 2 4
5
1 2 3 4 2 1
Компоненты сильной связности, метаграфы и мосты; компоненты двусвязности и точки сочленения
J: Компоненты сильной связности
Дан ориентированный граф.
Подмножество его вершин называется компонентой сильной связности,
если между любыми двумя вершинами существует путь в графе,
и в то же время ни одна другая вершина не может быть добавлена с сохранением этого свойства.
Выведите количество компонент сильной связности,
а затем — список вершин каждой компонты через пробел.
Отсортируйте вершины каждой компоненты в лексикографическом порядке,
а сами компоненты — в порядке возрастания "минимальной" вершины.
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\).
Вам задан ориентированный граф с $N$ вершинами и $M$ ребрами $(1\leqslant N\leqslant20000, 1\leqslant M\leqslant200000)$.
Стянем теперь каждую компоненту сильной связности в отдельную вершину (метавершину) и оставим только рёбра между метавершинами, удалив дубликаты.
Полученный граф называется метаграфом (meta-graph) исходного или его конденсацией.
Метаграф любого ориентированного графа является ациклическим и может быть топологически упорядочен.
Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Граф задан во входном файле следующим образом: первая строка содержит числа $N$ и $M$.
Каждая из следующих $M$ строк содержит описание ребра — два целых числа из диапазона от $1$ до $N$ — номера начала и конца ребра.
На первой строке выведите число $K$ — количество компонент сильной связности в заданном графе.
На следующей строке выведите $N$ чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина.
Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.
Дан неориентированный граф.
Его ребро называется мостом или перешейком,
если после его удаления количество компонент связности увеличивается.
Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
Выведите список мостов графа, отсортированный в лексикографическом порядке (вершины каждого ребра тоже солжны быть упорядочены).
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\).
7 8
1 2
2 3
2 4
2 5
3 5
4 5
5 6
7 4
1 2
4 7
5 6
4 3
1 2
2 3
3 4
1 2
2 3
3 4
6 7
1 2
2 3
3 1
2 4
4 5
5 6
6 4
2 4
M: Поиск точек сочленения
Дан неориентированный граф.
Его вершина называется шарниром или точкой сочленения,
если после её удаления количество компонент связности увеличивается.
Выведите список точек сочленения, отсортированный в лексикографическом порядке.
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\).
7 8
1 2
2 3
2 4
2 5
3 5
4 5
5 6
7 4
2
4
5
4 3
1 2
2 3
3 4
2
3
6 7
1 2
2 3
3 1
2 4
4 5
5 6
6 4
2
4
Алгоритм Дейкстры с кучей
Текст взят из книги «Алгоритмы» авторов С. Дасгупта, Х. Пападимитриу, У. Вазирани, перевод с английского А. С. Куликова под редакцией А. Шеня.
Пусть длины всех рёбер — натуральные числа. Тогда задачу поиска кратчайшего пути можно свести к случаю рёбер длины 1, расставив на всех дорогах
«верстовые столбы» и объявив их новыми вершинами (соответственно разбиваются и рёбра). Старые вершины и расстояния междуними останутся без
изменений, так что можно найти эти расстояния, запустив поиск в ширину
на новом графе.
Очевидный недостаток такого решения состоит в том, что при длинных рёбрах нужно много вспомогательных вершин, и алгоритм будет тратить много
времени, двигаясь от одного столба до другого.
Для примера рассмотрим граф $G$ и граф $G'$ с добавленными вершинами,
показанные на рисунке выше.
Запустим из $S$ поиск в ширину (со скоростью ребро за минуту).
Тогда первые $99$ минут он будет двигаться вдоль $S-A$ и $S-B$ от
столба к столбу. На это и смотреть скучно, так что мы лучше поспим до того момента, когда произойдёт что-то интересное (мы дойдём до настоящей
вершины). Поставим два будильника: один на время $100$ для вершины $A$, второй — на $200$ для $B$. Первый сработает раньше: поиск дойдёт сначала до вершины $A$.
Из $A$ начнётся новое движение, которое дойдёт до $B$ в момент $150$
(раньше, чем движение из $S$).
Опишем ситуацию в общем виде: поиск в ширину продвигается по рёбрам графа $G$, и для каждой вершины установлен будильник на ожидаемое
время прибытия уже запущенного движения. (Реально поиск может прийти
туда и раньше, пройдя через другую вершину, как это было в примере.) Главное: пока не сработает хотя бы один будильник, ничего интересного не будет (движение будет продолжаться по рёбрам). Звонок будильника означает,
что поиск в ширину добрался до некоторой вершины исходного графа $u \in V$.
В этот момент начинаются движения по рёбрам, исходящим из $u$, и это надо учесть в их концевых вершинах и перезавести будильники на концах этих
рёбер (если новое время прибытия раньше прежнего). Вот схема алгоритма:
- Завести будильник для $s$ на время $0$.
- Пока есть заведённые, но не сработавшие будильники:
--- Взять самый ранний из них (пусть он в вершине $u$ на момент $T$).
--- Констатировать, что расстояние от $s$ до $u$ равно $T$.
--- Для каждой вершины $v$, смежной с $u$ в $G$:
если для вершины $v$ будильник ещё не заведён, завести его на время
$T + l(u, v)$;
если будильник заведён на время, большее чем $T + l(u, v)$, то переставить его на это меньшее время (а иначе оставить как было).
Алгоритм с будильниками находит кратчайшие пути в графах с положительными целыми весами. Он практически готов к использованию, осталось только как-нибудь реализовать механизм будильников. Подходящая для
этих целей структура данных называется очередью с приоритетами; обычно
её реализуют с помощью кучи.
N: Длина кратчайшего пути: алгоритм Дейкстры
Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами $A$ и $B$.
Входные данные.
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа $N$ и $K$ ($1≤N≤100000$, $0≤K≤300000$), где $K$ – количество дорог. Каждая из следующих $K$ строк содержит описание дороги с двусторонним движением – три целых числа $a_{i}$, $b_{i}$ и $l_{i}$ ($1≤a_{i},b_{i}≤N$, $1≤l_{i}≤10^{6}$).
Это означает, что имеется дорога длины $l_{i}$, которая ведет из города $a_{i}$ в город $b_{i}.$ В последней строке находятся два числа $A$ и $B$ – номера городов, между которыми надо посчитать кратчайшее расстояние ($1≤A,B≤N$).
Выходные данные.
Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами.
Если по дорогам от города $A$ до города $B$ доехать невозможно, выведите –$1$.
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
115
O: Кратчайший путь: алгоритм Дейкстры
В условиях предыдущей задачи необходимо вывести любой из кратчайших путей.
Если пути между вершинами не существует, необходимо вывести число -1.
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
3 4 2 1
Алгоритм Прима с кучей
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе —
это остовное дерево этого графа, имеющее минимальный возможный вес (минимальную сумму весов входящих в него рёбер).
Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть $n$ городов,
которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города).
Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги.
Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.
Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе,
вершины которого представляют города, рёбра — это пары городов, между которыми можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.
Для находжения минимального остовного дерева можно использовать алгоритм Прима.
Он состоит в следующем: сначала покрасим все вершины и рёбра в серый цвет.
Возьмём любую вершину и покрасим в оранжевый цвет.
Оранжевые вершины — это в точности вершины, которые мы уже включили в наше остовное дерево.
Возьмём минимальную кучу и добавим в неё все рёбра, исходящие из текущей вершины (куча минимальная по весу ребра).
Покрасим все эти рёбра и вершины на их концах в чёрный цвет.
Чёрные рёбра — это все рёбра, которые «торчат» из вершин остовного дерева, по поводу которых мы ещё не определились.
Чёрные вершины — это все вершины, которые соединены ребром с текущей версией остовного дерева.
Подготовка завершена.
Теперь на каждом шагу мы извлекаем из кучи самое «лёгкое» чёрное ребро.
Если оно ведёт в оранжевую вершину, то красим его назад в серый цвет и забываем про него.
Если же оно ведёт в чёрную вершину, до добавляем это ребро в дерево: красим ребро и соответствующую вершину оранжевым,
а также красим в чёрный и добавляем в кучу все серые рёбра, идущие из этой новой вершины.
Концы этих новых чёрных рёбер тоже красим в чёрный цвет.
Когда куча опустеет, мы удивительным образом получим минимальное остовное дерево.
Асимптотика этого алгоритма — $O((V+E)\log V) = O(E \log V)$.
★ Докажите, что этот жадный алгоритм всегда работает и имеет именно такую асимптотику.
P: Минимальное остовное дерево: алгоритм Прима
Требуется найти в связном графе остовное дерево минимально веса.
Первая строка входного файла содержит два натуральных числа $N$ и $M$ — количество вершин и рёбер графа соответственно $(1\leqslant n\leqslant20000, 0\leqslant M\leqslant100000)$. Следующие $M$ строк содержат описание рёбер по одному на строке. Ребро номер $i$ описывается тремя натуральными числами $b_i,e_i$ и $w_i$ — номера концов ребра и его вес соответственно $(1\leqslant b_i,e_i\leqslant n,0\leqslant w_i\leqslant100000)$.
Выведите единственное целое число — вес минимального остовного дерева.
5 7
1 2 4
1 3 4
1 4 6
1 5 6
2 3 2
2 4 8
4 5 9
18
Разные задачи
Q: Вершины на путях
Дан неориентированный граф с $N$ вершинами и $M$ рёбрами, не содержащий петель и кратных рёбер. Кроме того дано несколько пар вершин $(a_i,b_i)$. Для каждой пары требуется найти количество вершин $c$, таких, что существует путь из $a_i$ в $b_i$, проходящий через вершину $c$.
Путь из $a$ в $b$ — это последовательность вершин, начинающаяся в $a$ и заканчивающаяся в $b$, такая, что каждые две соседние вершины этой последовательности соединены ребром. Обратите внимание, что путь может проходить по одной и той же вершине более одного раза.
В первой строке через пробел записаны два целых числа $n$ и $m~(1\leqslant n\leqslant100;0\leqslant m\leqslant n(n-1)/2)$ — количество вершин и рёбер графа. В следующих $m$ строках записано по два целых числа $u$ и $v~(1\leqslant u,v\leqslant n;u\ne v)$ — номера вершин, которые соединяет описываемое ребро.
В следующей строке записано единственное целое число $Q~(1\leqslant Q\leqslant10000)$ — количество пар $(a_i,b_i)$. В следующих $Q$ строках описываются пары. В $i$-й из этих строк через пробел записаны целые числа $a_i$ и $b_i~(a_i\ne b_i;1\leqslant a_i,b_i\leqslant n)$.
Для каждой описанной пары выведите на отдельной строке единственное число — количество вершин $c$, таких, что существует путь из $a_i$ в $b_i$, проходящий через $c$.
4 3
1 2
2 3
3 4
2
1 2
1 3
4
4
R: Рассадка (проверка графа на двудольность)
На банкет были приглашены $N$ Очень Важных Персон (ОВП). Были поставлены $2$ стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.
В первой строке входных данных содержатся два числа: $N$ и $M~(1\leqslant N,M\leqslant100)$, где $N$ — количество ОВП, а $M$ — количество пар ОВП, которые не могут сидеть за одним столом. В следующих $M$ строках записано по $2$ числа — пары ОВП, которые не могут сидеть за одним столом.
Если способ рассадить ОВП существует, то выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.
3 2
1 2
1 3
YES
1
S: Построение
Группа солдат-новобранцев прибыла в армейскую часть.
Прапорщик пронумеровал новобранцев числами от $1$ до $N$. После этого он велел им построиться по росту (начиная с самого высокого). При этом прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине.
После трёх дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен.
Сначала на вход программы поступают числа $N$ и $M~(1 < N\leqslant100,1\leqslant M\leqslant5000)$ — количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел $A$ и $B$ по одной на строке $(1\leqslant A,B\leqslant N)$, что означает, что, по мнению прапорщика, солдат $A$ выше, чем $B$. Не гарантируется, что все пары чисел во входных данных различны.
В первой строке выведите YES (если можно построиться так, чтобы прапорщик остался доволен) или NO (если нет). После ответа YES на следующей строке выведите $N$ чисел, разделенных пробелами, — одно из возможных построений.
4 5
1 2
2 3
3 4
1 4
4 1
NO
T: Количество путей
Дан ациклический ориентированный граф и несколько пар его вершин.
Определите количество простых путей (то есть путей, все рёбра которого попарно различны) из одной вершины в другую.
Так как это число может быть очень большим, то выведите его по модулю $10^9 + 7$.
Сложность получившегося алгоритма не считая сложности арифметических операций должна быть \(O(|V| + |E|)\).
(Например, количество путей в полном графе будет порядка \(n!\), для больших \(n\) арифметические операции с такими числами занимают существенное время)
7 8
1 2
2 3
2 4
2 5
3 5
4 5
5 6
7 4
3
2 5
2 1
7 6
3
0
1
U: Перегоны
На некоторой железнодорожной ветке расположено $N$ станций, которые последовательно пронумерованы числами от $1$ до $N$. Известны расстояния между некоторыми станциями. Требуется точно вычислить длины всех перегонов между соседними станциями или указать, что это сделать невозможно (то есть приведенная информация является противоречивой или ее недостаточно).
Во входном файле записаны сначала числа $N$ — количество станций $(2\leqslant N\leqslant10^5)$ и $E$ — количество пар станций, расстояния между которыми заданы $(0\leqslant E\leqslant10^5)$. Далее идет $E$ троек чисел, первые два числа каждой тройки задают номера станций (это числа из диапазона от $1$ до $N$), а третье — расстояние между этими станциями (все эти расстояния заданы точно и выражаются вещественными неотрицательными числами не более чем с 3-я знаками после десятичной точки).
В случае, когда восстановить длины перегонов можно однозначно, в выходной файл выведите сначала число $1$, а затем $N-1$ вещественное число. Первое из этих чисел должно соответствовать расстоянию от $1$-й станции до $2$-й, второе — от $2$-й до $3$-й, и так далее. Все числа должны быть выведены с точностью до $3$-х знаков после десятичной точки.
Если приведенная информация о расстояниях между станциями является противоречивой или не позволяет однозначно точно восстановить длины перегонов, выведите в выходной файл одно число $2$.
Дан неориентированный граф и две его вершины.
Выведите все рёбра, которые лежат на каком-либо кратчайшем пути от одной вершины до другой.
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\).
5 6
1 5
1 2
2 4
2 3
3 4
4 5
2 5
4 5
2 4
2 1
1 5
W: Вершины на кратчайшем пути
Дан неориентированный граф и две его вершины.
Выведите все вершины, которые лежат на каком-либо кратчайшем пути от одной вершины до другой (не считая начальной и конечной вершины).
Сложность получившегося алгоритма должна быть \(O(|V| + |E|)\).
5 6
1 5
1 2
2 4
2 3
3 4
4 5
2 5
1
4
X: Два коня
На стандартной шахматной доске $(8\times8)$ живут $2$ шахматных коня. Им нужно оказаться на одной клетке. Но наши шахматные кони ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы оказаться в одной клетке?
На вход программы поступают координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами — маленькая латинская буква (от a до h) и цифра (от $1$ до $8$), задающие столбец и строку соответственно).
Требуется вывести наименьшее необходимое количество ходов, либо число $-1$, если кони не могут встретиться.
a1 a3
1
Y: Циклы через рёбра
Дан неориентированный граф с $N$ вершинами и $M$ ребрами, не содержащий петель и кратных рёбер. Найдите количество рёбер графа, через которые можно провести цикл.
В первой строке через пробел записаны два целых числа $N$ и $M~ (1\leqslant n\leqslant100;0\leqslant m\leqslant n(n-1)/2)$ — количество вершин и ребер графа. В следующих $M$ строчках записано по два целых числа $a$ и $b~(1\leqslant a,b\leqslant n;a\ne b)$ — номера вершин, которые соединяет описываемое ребро.
Выведите единственное число — количество ребер графа, через которые можно провести цикл.
4 3
1 2
2 3
3 4
0
4 4
1 2
2 3
1 3
3 4
3
Z: Табличка
Дана таблица, состоящая из $N$ строк и $M$ столбцов. В каждой клетке таблицы записано одно из чисел: $0$ или $1$. Расстоянием между клетками $(x_1, y_1)$ и $(x_2, y_2)$ назовем сумму $|x1-x2|+|y1-y2|$. Вам необходимо построить таблицу, в клетке $(i,j)$ которой будет записано минимальное расстояние между клеткой $(i,j)$ начальной таблицы и клеткой, в которой записана $1$. Гарантируется, что хотя бы одна $1$ в таблице есть.
В первой строке вводятся два натуральных числа $N$ и $M$, не превосходящих $5000$. Далее идут $N$ строк по $M$ чисел — элементы таблицы.
Требуется вывести $N$ строк по $M$ чисел — элементы искомой таблицы.
2 3
0 0 1
1 0 0
1 1 0
0 1 1
ZA: Игрушечный лабиринт
Игрушечный лабиринт представляет собой прозрачную плоскую прямоугольную коробку, внутри которой есть препятствия и перемещается шарик. Лабиринт можно наклонять влево, вправо, к себе или от себя, после каждого наклона шарик перемещается в заданном направлении до ближайшего препятствия или до стенки лабиринта, после чего останавливается. Целью игры является загнать шарик в одно из специальных отверстий — выходов. Шарик проваливается в отверстие, если оно встречается на его пути (шарик не обязан останавливаться в отверстии).
Входные данные
В первой строке входного файла записаны числа $N$ и $M$ — размеры лабиринта (целые положительные числа, не превышающие $100$). Затем идет $N$ строк по $M$ чисел в каждой — описание лабиринта. Число $0$ в описании означает свободное место, число $1$ — препятствие, число $2$ — отверстие.
Выведите единственное число — минимальное количество наклонов, которые необходимо сделать, чтобы шарик покинул лабиринт через одно из отверстий.
4 5
0 0 0 0 1
0 1 1 0 2
0 2 1 0 0
0 0 1 0 0
3
ZB: Только направо
Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. Но Змей плохо соображает, поэтому может поворачивать направо и идти прямо, но не может поворачивать налево и разворачиваться на месте. Помогите Змею Горынычу определить длину кратчайшего пути до выхода из лабиринта.
В первой строке через пробел записаны числа $r$ и $c~(4\leqslant r, c\leqslant20)$ — количество строк и столбцов в карте лабиринта. В каждой из следующих $r$ строк записано по $c$ символов, задающих эту карту. Символ $S$ обозначает положение Змея Горыныча, символ $F$ — точку выхода из лабиринта, символ $X$ — стенку. Пробелами обозначены проходимые клетки. Гарантируется, что лабиринт окружен стенами. Перед началом движения Змей Горыныч может сориентироваться по любому из $4$ направлений (вверх, вниз, влево или направо).
Выведите единственное число — расстояние, которое придется пройти Змею Горынычу. Гарантируется, что он всегда сможет выйти из лабиринта.
10 14
XXXXXXXXXXXXXX
X XXX
X XFXXXXX X
XXX XX XX X
X S X
XX XXXXXX X X
X X X X
X X X X X
XXX XX X
XXXXXXXXXXXXXX
29
ZC: Наименьшее кратное
Дано число $X$ и множество цифр $D$. Требуется дописать к $X$ минимальное количество цифр из $D$, чтобы получившееся число делилось на $k$. При этом получившееся число должно быть минимально возможным.
Первая строка входного файла содержит два натуральных числа $X$ и $k~(1\leqslant X\leqslant10^{1000}, 2\leqslant k\leqslant10^5)$. Во второй строке записано количество цифр во множестве $D$. В третьей строке через пробел записаны эти цифры.
Единственная строка должна содержать минимальное число, полученное из $X$ дописыванием цифр из $D$ и кратное $k$. Если такого числа не существует, выведите $-1$.
102 101
3
1 0 3
10201
202 101
3
1 0 3
202
ZD: Военный поход
В одном феодальном государстве средневековой Европы было $n$ городов и $m$ дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно одного из тех, которые она соединяла). Однажды правитель города $S$ решил объявить войну правителю города $T$. Перед ним сразу же встала задача: как довести армию до города $T$.
Правитель каждого города требует плату за проход войск через его город. Кроме того, правитель города $S$ может перемещать войска только по дорогам, которые принадлежат ему. При этом он может купить любую дорогу у её владельца за определенную плату (даже если владелец — правитель города $T$). К сожалению, все деньги из казны города $S$ были потрачены на предыдущий неудачный военный поход, поэтому сначала правителю придется продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска).
Помогите правителю выяснить, какие дороги следует продать, а какие купить, чтобы довести войска от города $S$ до города $T$ и оплатить проход через все промежуточные города. Все операции продажи и покупки дорог надо осуществить до начала похода, пока правители других городов не догадались о воинственных намерениях правителя города $S$.
В первой строке вводятся целые числа $n$ и $m$ — количество городов и дорог соответственно $(2\leqslant n\leqslant2000, 1\leqslant m\leqslant50000)$. Города нумеруются от $1$ до $n$, города $S$ и $T$ имеют номера $1$ и $n$ соответственно.
Следующие $n$ строк содержат под одному целому числу $r_i$ — плату за проезд через город $i~(0\leqslant r_i\leqslant10000,r_1=r_n=0)$.
Далее идут $m$ строк, задающих описания дорог. Дорога описывается четырьмя целыми числами: $a_i,b_i,p_i$ и $c_i$. Здесь $a_i$ и $b_i$ — номера городов, которые соединяет дорога, $p_i$ — номер города, правителю которого она принадлежит, $c_i$ — её стоимость $(a_i\ne b_i,1\leqslant c_i\leqslant10000)$. По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более, чем одной дорогой.
В первой строке выведите список дорог, которые нужно продать, в следующем формате: сначала число дорог, а затем их номера. Дороги нумеруются с единицы в том порядке, в котором они заданы во входных данных. Во второй строке выведите список дорог, которые нужно купить, в том же формате. В третьей строке выведите маршрут похода — номера городов в порядке следования войска. Если решений несколько, выведите любое.
Если решения нет, выведите число $-1$.
3 3
0
1
0
1 2 1 10
2 3 1 10
3 1 2 2
2 1 2
1 3
1 3
ZE: Алфавит
Страна $X$ использует при письме маленькие буквы латинского алфавита. Однако упорядочивают их в другом порядке.
Вам дан набор слов. Необходимо восстановить порядок букв в алфавите таким образом, чтобы данные слова оказались упорядоченными по возрастанию в лексикографическом порядке. Если порядок существует, но его нельзя восстановить однозначно — нужно вернуть любой подходящий порядок букв. Если не существует порядка букв, удовлетворящего условию задачи — вывести $-1$.
В первой строке входных данных указано количество слов $(N < 1000)$. Затем $N$ строк с одним словом на каждой. Суммарная длина слов не превосходит $10000$.
Программа должна вывести одну строку: упорядоченную последовательность букв без разделителей, либо -1.
В последовательности букв должны встретиться обязательно все буквы из набора слов и никаких других букв.
3
abc
bc
bb
acb
ZF: Проверка обхода в глубину
Дан неориентированный граф и некоторая последовательность номеров его вершин. Определить — может ли эта последовательность вершин быть результатом работы программы, перечисляющей вершины графа в порядке его обхода в глубину?
В первой строке через пробел записаны два целых числа $N$ и $M~ (1\leqslant n\leqslant10^5;0\leqslant m\leqslant 10^6$ — количество вершин и ребер графа. В следующих $M$ строчках записано по два целых числа $a$ и $b~(1\leqslant a,b\leqslant n;a\ne b)$ — номера вершин, которые соединяет описываемое ребро.
В следующей строке записано число $Q$ — количество запросов. Наконец, в каждой из следующих $Q$ строк записана последовательность чисел $a_i~ (1\leqslant a_i\leqslant N)$.
Программа должна вывести $Q$ строк: в $i$-й строке следует вывести \YES, если последовательность $a_i$ может быть получена при выполнении обхода в глубину на данном графе начиная с какой-то вершины в каком-то порядке обхода и \NO, если не может быть получена ни при каком порядке обхода.
3 2
1 2
3 2
2
1 2 3
3 1 2
YES
NO
4 2
1 2
3 4
1
1 3 2 4
NO
ZG: Безопасность данных
Телекоммуникационная сеть крупной IT-компании содержит $n$ серверов,
пронумерованных от $1$ до $n$. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети $m$ каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.
Множество серверов $A$ называется отказоустойчивым, если при недоступности
любого канала связи выполнено следующее условие: для любого не входящего в это
множество сервера $X$ существует способ передать данные по остальным каналам на сервер $X$ хотя бы от одного сервера из множества $A$.
На иллюстрации ниже показан пример сети и отказоустойчивого множества из серверов с номерами $1$ и $4$. Данные на сервер $2$ можно передать следующим образом. При недоступности канала между серверами $1$ и $2$ — с сервера $4$, при недоступности канала между серверами $2$ и $3$ — с сервера $1$. На серверы $3$ и $5$ при недоступности любого канала связи можно по другим каналам передать данные с сервера $4$.
В рамках проекта группе разработчиков компании необходимо разместить свои
данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число $10^9+7$.
Требуется написать программу, которая по заданному описанию сети определяет следующие числа: $k$ — минимальное количество серверов в отказоустойчивом множестве серверов, $c$ — остаток от деления количества способов выбора отказоустойчивого множества из $k$ серверов на число $10^9+7$.
Первая строка входного файла содержит целые числа $n$ и $m$ — количество серверов и количество каналов связи соответственно $(2\leqslant n\leqslant200000, 1\leqslant m\leqslant200000)$.
Следующие $m$ строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.
Гарантируется, что любые два сервера соединены напрямую не более чем одним
каналом связи, никакой канал не соединяет сервер сам с собой, и для любой пары серверов существует способ передачи данных с одного из них на другой, возможно с использованием одного или нескольких промежуточных серверов.
Выведите два целых числа, разделенных пробелом: $k$ — минимальное число серверов в отказоустойчивом множестве серверов, $c$ — количество способов выбора отказоустойчивого множества из $k$ серверов, взятое по модулю $10^9+7$.
5 5
1 2
2 3
3 4
3 5
4 5
2 3
ZH: Важные вершины
Дан неориентированный граф с $N$ вершинами и $M$ рёбрами, не содержащий петель и кратных рёбер. Так же вам дано несколько пар вершин $(a_i,b_i)$. Для каждой пары требуется найти количество вершин $c~(c\ne a_i;c\ne b_i)$, таких, что любой путь из $a_i$ в $b_i$, если такой существует, проходит через вершину $c$.
Путь из $a$ в $b$ — это последовательность вершин, начинающаяся в $a$ и заканчивающаяся в $b$, такая, что каждые две соседние вершины этой последовательности соединены ребром. Обратите внимание, что путь может проходить по одной и той же вершине более одного раза.
В первой строке через пробел записаны два целых числа $N$ и $M$ — количество вершин и ребер графа, где $1\leqslant N\leqslant400;0\leqslant M\leqslant\dfrac{n(n-1)}{2}$.
В следующих $M$ строках записано по два целых числа $u$ и $v~ (1\leqslant u,v\leqslant n;u\ne v)$ — номера вершин, которые соединяет описываемое ребро.
В следующей строке записано единственное целое число $Q~(1\leqslant Q\leqslant10000)$ — количество пар $(a_i,b_i)$. В следующих $Q$ строках описываются пары. В $i$-й из этих строк через пробел записаны целые числа $a_i$ и $b_i~(a_i\ne b_i;1\leqslant a_i,b_i\leqslant n)$.
Для каждой описанной пары выведите на отдельной строке единственное число — количество вершин $c$, таких, что любой путь из $a_i$ в $b_i$, проходит через $c$.
