635
правок
Изменения
→Задача о динамической связности
* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u</tex> и <tex>w</tex> одной компоненте связности.
}}
Для решения поставленной задачи будем представлять дерево в виде его эйлерова обхода. Это позволит выполнять указанные запросы за <tex>O(\log n)</tex>.
{{Определение
|definition = '''Дерево эйлерова обхода''' (англ.''Euler tour tree'') {{---}} способ представления динамического дерева, позволяющий выполнять указанные запросы за <tex>O(\log n)</tex>.
