Изменения

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

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

48 байт добавлено, 01:22, 7 июня 2014
Нет описания правки
bool visited[n];
vector <'''int'''> query[n];
'''int ''' dsu_get ('''int ''' v)
'''if''' (v == dsu[v])
'''return''' v
unite ('''int ''' a, '''int ''' b, '''int ''' new_ancestor)
a = dsu_get (a);
b = dsu_get (b);
dfs('''int ''' v) visited[v] = '''true''';
'''for''' (u таких, что (v, u) — ребро в G)
'''if''' (not visited[u])
Анонимный участник

Навигация