Изменения

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

52 байта добавлено, 01:16, 7 июня 2014

Нет описания правки

int dsu_get (int v)

~~return~~ '''if''' (v == dsu[v] ? ) '''return''' v : '''else''' '''return''' dsu[v] = dsu_get (dsu[v]);

dfs(int v)

visited[v] = true;

'''for ''' (u таких, что (v, u) — ребро в G)

'''if''' (not visited[u])

dfs(u);

union(v, u, v);

for (i = 0; i < query[v].size; i++)

'''if ''' (visited[query[v][i]])

cout << "LCA " << v << " " << u << " = " << ancestor[dsu_get(q[v][i])];

~~int main()~~ dfs(1); // можно запускать от любой вершины

74

правки