обратная операция к «Объединить и найти»

Мы знаем, что для непересекающихся множеств существует метод «Объединить и найти». http://en.wikipedia.org/wiki/Union_find

Но как сделать обратную операцию? Рассмотрим набор из N узлов, соединенных E ребрами (который на самом деле является графом). И на каждом шаге мы хотим удалить какое-то ребро и проверить, приводит ли эта операция удаления к другому непересекающемуся множеству. Можно ли сделать это быстро, как в «Объединяй и найди»?

P.S это не домашнее задание, у нас праздник :)