Для того, чтобы проверить, лежат ли 2 вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот элеров обход.
==Реализация Способы реализации структуры==
Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать поиска, например, в виде [[Красно-черное дерево|красно-черное деревочерного дерева]].
[[Файл:Balanced tree.png |center]] Объединение Операции объединения и разделение разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.]</ref>. Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за <tex>O(1)</tex>. Запрос о принадлежности вершин к одной компоненте связности выполняется за <tex>O(\log n)</tex> проверкой лежат ли эти вершины в одном дереве. [[Файл:Balanced tree1.png |center]]
==См. также==
