Мы знаем, что для непересекающихся множеств существует «Объединение и поиск». http://en.wikipedia.org/wiki/Union_find
Но как сделать обратную операцию? Рассмотрим набор с N узлами, соединенными с E ребрами (который на самом деле является графом). И на каждом шаге мы хотим удалить какое-то ребро и проверить, не приведет ли эта операция удаления к другому непересекающемуся множеству. Можно ли сделать это быстро, как в "Союз и находка"?
P.S. это не домашнее задание, у нас праздник :)
Это известно как проблема удаления границы в сети или проблема с подключением к сети. Некоторые ссылки на алгоритмы находятся в этом статье Википедии о связности графов. .
Итак, ваш вопрос заключается в том, как эффективно обнаружить Мост? Это можно сделать за линейное время (см. также ссылку).
Union-find используется в алгоритме Крускала, который многократно добавляет ребро минимального веса, не образующее цикла. Обратная идея — удаление ребер максимального веса до тех пор, пока это не разъединяет граф — используется в алгоритм обратного удаления, который, по-видимому, может использовать некоторую сложную структуру данных (см. Википедию).
