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

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

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

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

Ответы

Ответ 1

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

Ответ 2

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

Ответ 3

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