Изменения

Перейти к: навигация, поиск

Деревья Эйлерова обхода

687 байт убрано, 16:21, 4 декабря 2016
→‎Реализация структуры
{{Задача
|definition = Реализовать добавление и разрезание ребер, а также проверку принадлежности вершин одной компоненте связности Определить структуру данных для хранения эйлеровых обходов деревьев для наиболее эффективным образомэффективного выполнения указанных операций.
}}
 
By representing trees via their Euler tours, can implement link and cut so that only O(1) joins and splits are necessary per operation.
 
Questions to answer:<br>
How do we efficiently implement these joins and splits?<br>
Once we have the tours, how do we answer connectivity queries?
 
Implementing the Structure
 
The operations we have seen require us to be able to efficiently do the following:<br>
Identify the first and last copy of a node in a sequence.<br>
Split a sequence at those positions.<br>
Concatenate sequences.<br>
Add a new copy of a node to a sequence.<br>
Delete a duplicate copy of a node from a sequence.<br>
How do we do this efficiently?
Sokolova
635
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/56880»

Навигация