Добрый вечер!
Не подскажете, видел ли кто-нибудь
свободный C или C++ исходник где эффективно реализована динамическая двусвязность? У меня ощущение что придется писать собственный код, но поскольку алгоритмы достаточно громоздкие, хочется сначала убедиться что нет ничего готового
Задача такая. Граф неориентир., ребра постепенно удаляются неким процессом, перед удалением очередного ребра требуется знать (за время меньшее чем O(E)) не приведет ли удаление к дисконнекту.
Заранее спасибо если кто-то чего-то подскажет.
-- Пн авг 10, 2009 01:03:52 --PS. В принципе исходники по динамической 1-связности не помешают тоже
Ведь моя задача слабее чем 2-связность в общем виде. Если у меня есть алгоритм для 1-связности работающий полностью динамически то я могу сначала удалить линк потом проверить и затем если надо вернуть на место.
09.08.2009, 23:50 