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