635
правок
Изменения
→Реализация структуры
}}
При представлении деревьев в виде их эйлерова обхода выполнение каждой операции <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> сводится к <tex>O(1)</tex> соединений и разбиений отрезков в последовательности вершин эйлерова обхода.
Рассмотрим следующие структуры данных для определения времени выполнения разбиения и соединения последовательностей, а также определение принадлежности вершин одной компоненте связности.
