Задачник Базовый курс EN

Есть ли такой участок

граф хеш-таблица оценка карты и навигация

Дан граф улиц: перекрёстки пронумерованы от 0 до n − 1, участки улиц соединяют пары перекрёстков (участок можно проехать в обе стороны; бывают и параллельные участки между одними перекрёстками). На каждый вопрос «есть ли участок между перекрёстками u и v» ответьте YES или NO.

Второй и третий тесты — улицы центра Алматы из OpenStreetMap: 7909 перекрёстков и 10 423 участка. В последних тестах перекрёстков 200 000 — прикиньте, сколько памяти займёт матрица смежности.

Вход

В первой строке n, m и q (1 ≤ n ≤ 2·10⁵, 0 ≤ m, q ≤ 2·10⁵). Дальше m строк с концами участков и q строк с вопросами — по два номера перекрёстков.

Выход

На каждый вопрос — YES или NO.

Примеры

Пример 1

Вход

Выход

YES
YES
NO
NO
YES

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 5 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Матрица смежности отвечает на такой вопрос за одно обращение. Сколько она займёт при n = 2·10⁵, если клетка — один байт? А если бит?

2Идея

Матрица — 4·10¹⁰ клеток: 40 гигабайт байтами и 5 гигабайт битами, а рёбер всего 2·10⁵. Достаточно хранить сами рёбра — пары (u, v) с меньшим концом первым — в хеш-множестве. Вопрос — тоже упорядоченная пара и поиск в множестве.

3Разбор

Порядок концов важен: участок 3–7 должен находиться и по вопросу «7 3». Удобно ключом сделать одно число: меньший конец, сдвинутый на 20 бит влево, плюс больший (номера меньше 2²⁰). Второй хороший способ — списки смежности, отсортированные, и двоичный поиск в списке меньшей вершины: O(log deg) на вопрос и никакого хеширования.

Вопрос «есть ли участок от перекрёстка к нему самому» — законный, ответ NO: петель в графе нет.

3+Решение

4Сложность

O(m) памяти и O(m + q) времени в среднем. С отсортированными списками — O(m log m) на построение и O(log deg) на вопрос.

5Типичные ошибки

Матрица. На Алматы она поместится (62 МБ байтами), на 2·10⁵ вершин — нет.
Пара в одном порядке. Ребро 3–7, записанное как (3, 7), не найдётся по вопросу (7, 3), если не упорядочить концы.
Просмотр всех рёбер на каждый вопрос. O(m·q) = 4·10¹⁰.

Алгоритмы задачи

GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево.

соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков

2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи