Обсуждение:Построение компонент рёберной двусвязности — различия между версиями
м (Дмитрий Мурзин переименовал страницу Обсуждение:Построение компонент реберной двусвязности в [[Обсуждение:Построение компонент рёбе…) |
|||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 5: | Строка 5: | ||
Граф: | Граф: | ||
| − | + | 8 вершин, 10 ребер {(1 2), (2 8), (8 1), (2 3), (3 4), (4 5), (5 3), (3 6), (6 7), (7 3)} | |
| − | 1 2 | ||
| − | 2 8 | ||
| − | 8 1 | ||
| − | 2 3 | ||
| − | 3 4 | ||
| − | 4 5 | ||
| − | 5 3 | ||
| − | 3 6 | ||
| − | 6 7 | ||
| − | 7 3 | ||
Текущая версия на 23:48, 31 января 2019
"ИТОГО: раньше часть про однопроходный алгоритм выглядела более правдоподобной."
Хм.. не согласен, если про работоспособность, то это не факт. То что описано здесь, работает и было сдано на Лабораторной по АСД. Могу код привести реальный. Да и с точки зрения асимптотики, это лучше и не скрыто в коде асимптотика СНМ. Кроме того этот алгоритм, в отличие от решения СНМ, реализацию на стеке была рассказана на практике, в качестве домашнего задания.
Граф:
8 вершин, 10 ребер {(1 2), (2 8), (8 1), (2 3), (3 4), (4 5), (5 3), (3 6), (6 7), (7 3)}
