635
правок
Изменения
→Реализация структуры
Каждое разбиение и соединение последовательностей требует О<tex>O(1)</tex>.
Для каждой вершины будем хранить указатели на первое и последнее вхождение вершины в последовательность. Тогда возможно определять первое и последнее вхождение вершины за О<tex>O(1)</tex>.
Однако,используя двусвязные списки определение принадлежности вершин одной компоненте связности занимает О(n) в худшем случае.
