Последний узел в обходе графа с Q-запросами

Question

Учитывая ориентированный граф с N узлами (1 <= N <= 100000) Каждый узел будет иметь только один исходящий ребро, но может быть более одного входящего ребра. Есть Q (1 <= Q <= 10 ^ 5) запросов, каждый из которых имеет 2 типа. </p>

1. В первом запросе мы должны указать, начнем ли мы прохождение графа с узла «А», то есть последнего узла, на котором мы остановились. Если мы никогда не остановимся, вернем -1.
2. Второй тип запроса заключается в том, что мы можем удалить исходящие ребра узла 'A'

Я знаю, что мы можем решить этот вопрос по сложности O (N) на запрос (с общей сложностью QN), но так как число запросов невелико (10 ^ 5), это не кажется эффективным решением?

Есть идеи, как решить эту проблему с лучшей временной сложностью? Спасибо

Answer 1

Если вам не нужно отвечать на запросы в режиме онлайн, проще всего реализовать объединение поиска с сжатием пути и обработать ввод в обратном направлении. Инициализируйте, связав каждую дугу, которая никогда не удаляется (с особым случаем ниже). Сканируя в обратном направлении, для запроса второго типа, добавьте дугу, если это не создаст цикл, и в этом случае свяжите хвост со специальной вершиной с идентификатором -1. Чтобы ответить на первый вид запроса, найдите корень со сжатием пути. Время выполнения будет O ((Q + N) log N).