Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
cut u v — удалить из графа ребро u - v;ask u v — проверить, лежат ли две вершины u и v в одной компоненте связности.Известно, что после выполнения всех операций типа
cut, рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.Входные данные.
В первой строке дают три числа n, m, k.
После m пар чисел задающая ребра графа. После k запросов.
Решение:
Тинькофф любит давать задачи на СНМ.
Во первых заметим, что в конце всех запросов граф станет пустой, этот факт нам очень сильно поможет.
Давайте запросы обрабатывать с конца, то есть сначала k тый запрос, после k-1 и тд до 1 запроса.
Такой подход называется решения оффлайн, так как сначала введем все запросы, а дальше решаем задачу.
И так в конце после всех запросов наш граф пустой, давайте построим СНМ где компонента это отдельная вершина. После когда приходит запрос cut u, v мы будем добавлять вершины u, v в одно множество, а при ask u, v будем узнавать правда ли вершины в одной компоненте.
Стандартное решение с помощью СНМ, главное нужно было заметить, что задачу можно решать оффлайн.
Время работы O(k*logn).
Код в комментариях.