Изменения

Перейти к: навигация, поиск

Алгоритм Тарьяна поиска LCA за О(1) в оффлайне

11 байт добавлено, 02:08, 6 июня 2014
Нет описания правки
Тогда заметим что ответ - это либо вершина <tex>v</tex>, либо какой-то её предок. Значит нам нужно найти предок вершины <tex>v</tex>, который является предком вершины <tex>u</tex> с наибольшей глубиной. Заметим, что при фиксированном <tex>v</tex> каждый из предков вершины <tex>v</tex> порождает некоторый класс вершин <tex>u</tex>, для которых он является ответом (в этом классе содержатся все вершины которые находятся "слева" от этого предка).
На рисунке разные цвета-разные классы,а белые вершины ещё не просмотренные в <tex>dfs</tex>.
Классы этих вершин - не пересекаются, а значит мы их можем эффективно обрабатывать с помощью <tex>dsu</tex>.
74
правки

Навигация