Изменения
Нет описания правки
Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, если все запросы известны заранее (offline).
Каждый запрос к дереву {{---}} это </tex>2</tex> вершины <tex>v</tex>,<tex>u</tex> для которых нужно найти такую вершину <tex>k</tex>, что <tex>k</tex>{{---}} предок вершин <tex>v</tex> и <tex>u</tex>, и <tex>k</tex> имеет максимальную глубину из всех таких вершин.Алгоритм позволяет найти ответы для дерева из <tex>n </tex> вершин и <tex>m </tex> запросов за время <tex>O (n + m)</tex>, т.е при достаточно большом <tex>m</tex>, за <tex>O (1)</tex> на запрос.
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим [[Обход в глубину, цвета вершин|обход в глубину]] из её.
На рисунке разные цвета {{---}} разные классы,а белые вершины ещё не просмотренные в <tex>dfs</tex>.
Классы этих вершин не пересекаются, а значит мы их можем эффективно обрабатывать с помощью [[СНМ (реализация с помощью леса корневых деревьев)|dsuсистемы непересекающихся множеств]], которую будем храниться в массиве <tex>dsu</tex>.
Будем поддерживать массив <tex>ancestor[v]</tex> {{---}} представитель множества в котором содержится вершина <tex>v</tex>.
'''function ''' union(a : '''int''', b : '''int''', newAncestor : '''int''' ):
a = dsuGet(a)
b = dsuGet(b)
ancestor[b] = newAncestor
<font color=green>//можно запустить от любой вершины дерева.</font> '''function ''' dfs(v : '''int'''):
visited[v] = ''true''
'''foreach''' u : (v, u) '''in''' G
