Обсуждение:Построение компонент рёберной двусвязности

Материал из Викиконспекты
Перейти к: навигация, поиск

"ИТОГО: раньше часть про однопроходный алгоритм выглядела более правдоподобной."

Хм.. не согласен, если про работоспособность, то это не факт. То что описано здесь, работает и было сдано на Лабораторной по АСД. Могу код привести реальный. Да и с точки зрения асимптотики, это лучше и не скрыто в коде асимптотика СНМ. Кроме того этот алгоритм, в отличие от решения СНМ, реализацию на стеке была рассказана на практике, в качестве домашнего задания.


Граф: 8 10 //8 вершин, 10 ребер 1 2 2 8 8 1 2 3 3 4 4 5 5 3 3 6 6 7 7 3