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

Материал из Викиконспекты
Перейти к: навигация, поиск

Введение

Динамические деревья (англ.dynamic tree) используются в двух областях:.........

Нужно поддерживать следующие операции

  • [math]\mathrm{isConnected(u, w)}[/math] — принадлежат ли вершины u и w одной компоненте связности,
  • [math]\mathrm{link(u, w)}[/math] — добавить ребро (u, w) (при условии, что ребро u w принадлежат разным деревьям)
  • [math]\mathrm{cut(u, w)}[/math] — разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву)[math]\mathrm{v}[/math].