Изменения

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

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

5 байт добавлено, 17:26, 9 июня 2014
Реализация
'''bool''' visited[n]
vector<'''int'''> query[n]
'''function''' union(x : '''int''', y : '''int''', newAncestor : '''int'''):
dfs(u)
union(v, u, v)
'''forforeach''' i = 0 '''to''' query[u : <tex>\langle v].size , u \rangle </tex> {{--- 1}} есть такой запрос '''if''' visited[query[v][i]u] запомнить, что ответ для запроса <tex>\langle v, u \rangle </tex> = ancestor[find[q[v][i]u]]
== Корректность ==

Навигация