Привет, Codeforces!
Недавно я столкнулся с интересной задачей, но не могу ее решить.
Дан неориентированный граф, состоящий из n вершин и m ребер. Так же имеется k запросов 2-x типов :
Для запроса 1-го типа имеется два числа x и y. Надо удалить ребро между вершинами x и y (если оно есть).
Для запроса 2-го типа так же имеется два числа x и y. Надо проверить лежат ли вершины x и y в одной компоненте связности.
N <= 50000, M <= 100000, K <= 150000
Тема этой задачи — СНМ. Но я пока что все равно не понимаю как можно решать эту задачу через СНМ если у нас граф может быть любым.
Буду очень благодарен за любую подсказку.
UPD: Решил. Всем спасибо).
А какие ограничения на n и m?
И скинь задачу, может там подробности какие-нибудь есть
N <= 50000, M <= 100000, K <= 150000
Это стандартная техника на СНМ. Надо прочитать все запросы и идти с конца по ним. Для каждого ребра запомним последний момент, когда оно было в графе (если оно не удалялось, то пусть этот момент будет $$$m+2$$$). И получается все, идем с конца в начало по запросам и добавляем ребра в граф попутно сохраняя ответы на запросы и потом выводя их в правильной последовательности. Работает за $$$O(M + N)$$$, если добавить оптимизацию сжатию путей и объединение по рангу, то СНМ будет работать в среднем за обратную функцию Акермана, которая растет очень медленно, и можно считать что она равна $$$O(1)$$$ всегда.
Если речь идёт про эту задачу D. Разрезание графа, то ты не указал очень важную часть условия:
Будем выполнять запросы в обратном порядке, тогда операция
cut u vбудет соответствовать добавлению ребра между вершинами u и v, аask u vпроверке лежат ли вершины u и v в одной компоненте связности — всё это легко поддерживать обычным СНМом.Ого. Точно, спасибо. Думал что это условие неважно.
Это условие неважно. Если в конце остались рёбра, можно поступить двумя способами (которые по сути эквивалентны). Первый способ: добавить в конце фейковые запросы
cut, которые удалят все оставшиеся рёбра. Второй способ: просто перевернуть все запросы и применить к СНМ, однако начальное состояние СНМ сделать не из пустого графа, а из графа, который получится после всех запросов (то есть из графа, содержащего те рёбра, которые были в изначальном графе и не были удалены запросами). Чтобы получить это состояние, нужно просто вызвать в СНМjoinот всех пар вершин, которые в конечном графе соединены рёбрами.Автор, обрати внимание, что на самом деле в задаче рассматривается неориентированный граф (а не ориентированый, как написано в условии). У ориентированых графов нет корректно определённого понятия «компонента связности».