обратная операция "Союз и найди"

Question

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

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

П.С. это не домашняя работа, у нас праздник:)

Answer 1

Это известно как проблема удаленного доступа к сети или проблема с подключением к сети.Некоторые ссылки на алгоритмы находятся в этом разделе статьи Википедии о связности графов .

Answer 2

Union-find используется в алгоритме Крускала, который многократно добавляет ребро минимального веса, которое не составляет цикл.Обратная идея - удаление ребер с максимальным весом до тех пор, пока он не отсоединяет граф - используется в алгоритм обратного удаления , который, по-видимому, может использовать некоторую сложную структуру данных (см. Википедия).

Answer 3

Итак, ваш вопрос заключается в том, как эффективно обнаружить Мост ?Это можно сделать за линейное время (см. Также ссылку).