E050. Lowest common ancestor. Нахождение за в оффлайн (Algorithmus Тарьяна)
Источник: e-maxx.ru/algo, страница PDF 147.
given Baum
с
vertexми и given
запросов вида
. Для каждого запроса
it is required
find наименьшего общего предка вершин
и
, т.е. такую вершину
, которая наиболее удалена от корня дерева,
и при этом является предком обеих вершин
и
. Мы рассматриваем задачу в режиме оффлайн, т.е. считая, что все запросы известны заранее. Описываемый
ниже Algorithmus позволяет ответить на все
запросов за суммарное время
, т.е. при достаточно
большом
за
на запрос.
Algorithmus Тарьяна
Основой для Algorithmusа является структура данных "Disjoint set union", которая и была изобретена Тарьяном (Tarjan). Algorithmus фактически представляет собой обход в глубину из корня дерева, в процессе которого постепенно
находятся ответы на запросы. А именно, ответ на запрос
находится, когда обход в глубину находится в вершине
, а vertex
уже была посещена, или наоборот.
Итак, пусть обход в глубину находится в вершине
(и уже были выполнены переходы в её сыновей), и оказалось, что
для какого-то запроса
vertex
уже была посещена обходом в глубину. Научимся тогда находить
этих двух вершин.
Заметим, что
является либо самой вершиной
, либо одним из её предков. Получается, нам надо
find самую нижнюю вершину среди предков
(включая её саму), для которой vertex
является потомком.
Заметим, что при фиксированном
по такому признаку (т.е. какой наименьший предок
является и предком какой-
то вершины) вершины дерева дерева распадаются на совокупность непересекающихся классов. Для каждого
предка
вершины
её класс содержит саму эту вершину, а также все поддеревья с корнями в тех её
сыновьях, которые лежат "слева" от пути до
(т.е. которые были обработаны ранее, чем была достигнута
). Нам надо научиться эффективно поддерживать все эти классы, для чего мы и применим структуру данных "Disjoint set union". Каждому классу будет соответствовать в этой структуре множество, причём
для представителя этого множества мы определим величину
— ту вершину
, которая и образует
этот класс. Рассмотрим подробно реализацию обхода в глубину. Пусть мы стоим в некоторой вершине
. Поместим её в
отдельный класс в структуре непересекающихся множеств,
. Как обычно в обходе в
глубину, перебираем все исходящие рёбра
. Для каждого такого
мы сначала должны вызвать обход в
глубину из этой вершины, а потом добавить эту вершину со всем её подBaumм в класс вершины
. Это
реализуется операцией
структуры данных "Disjoint set union", с последующей
установкой
для представителя множества (т.к. после объединения представитель класса мог измениться). Наконец, после обработки всех рёбер мы перебираем все запросы вида
, и если
была
помечена как посещённая обходом в глубину, то ответом на этот запрос будет
vertex
. Нетрудно заметить, что для каждого запроса
это Beschreibung (что одна vertex запроса является текущей, а другая была посещена ранее) выполнится ровно один раз. Оценим асимптотику. Она складывается из нескольких частей. Во-первых, это Asymptotic complexity обхода в
глубину, которая в данном случае составляет
. Во-вторых, это операции по объединению множеств, которые
в сумме для всех разумных
затрачивают
операций. В-третьих, это для каждого запроса проверка условия
(два раза на запрос) и Definition результата (один раз на запрос), каждое, опять же, для всех разумных
выполняется за
. Итоговая Asymptotic complexity получается
, что означает для достаточно больших
(
) ответ за
на один запрос.
Implementierung
Приведём полную реализацию данного Algorithmusа, включая слегка изменённую (с поддержкой ) реализацию системы пересекающихся множеств (рандомизированный варианта).
const int MAXN = максимальное number вершин в Graphе;
vector<int> g[MAXN], q[MAXN]; // Graph и все запросы
int dsu[MAXN], ancestor[MAXN];bool u[MAXN];
int dsu_get (int v) {return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]);}
void dsu_unite (int a, int b, int new_ancestor) {
a = dsu_get (a), b = dsu_get (b);
if (rand() & 1) swap (a, b);dsu[a] = b, ancestor[b] = new_ancestor;
}
void dfs (int v) {
dsu[v] = v, ancestor[v] = v;
u[v] = true;
for (size_t i=0; i<g[v].size(); ++i)if (!u[g[v][i]]) {dfs (g[v][i]);
dsu_unite (v, g[v][i], v);
}
for (size_t i=0; i<q[v].size(); ++i)if (u[q[v][i]]) {printf ("%d %d -> %d\n", v+1, q[v][i]+1,
ancestor[ dsu_get(q[v][i]) ]+1);
}
int main() {... чтение Graphа ...
// чтение запросов
for (;;) {int a, b = ...; // очередной запрос--a, --b;
q[a].push_back (b);
q[b].push_back (a);
}
// обход в глубину и ответ на запросы
dfs (0);
}
C# Lösung
Auto-Entwurf, vor dem Einreichen prüfenusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
const int MAXN = максимальное число вершин в графе;
List<int> g[MAXN], q[MAXN]; // граф и все запросы
int dsu[MAXN], ancestor[MAXN];
bool[] u = new bool[MAXN];
int dsu_get (int v) {
return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]);
}
void dsu_unite (int a, int b, int new_ancestor) {
a = dsu_get (a), b = dsu_get (b);
if (rand() & 1) swap (a, b);
dsu[a] = b, ancestor[b] = new_ancestor;
}
void dfs (int v) {
dsu[v] = v, ancestor[v] = v;
u[v] = true;
for (size_t i=0; i<g[v].size(); ++i)
if (!u[g[v][i]]) {
dfs (g[v][i]);
dsu_unite (v, g[v][i], v);
}
for (size_t i=0; i<q[v].size(); ++i)
if (u[q[v][i]]) {
Console.Write ("%d %d -> %d\n", v+1, q[v][i]+1,
ancestor[ dsu_get(q[v][i]) ]+1);
}
int main() {
... чтение графа ...
// чтение запросов
for (;;) {
int a, b = ...; // очередной запрос
--a, --b;
q[a].push_back (b);
q[b].push_back (a);
}
// обход в глубину и ответ на запросы
dfs (0);
}
}C++ Lösung
zugeordnet/originalconst int MAXN = максимальное число вершин в графе;
vector<int> g[MAXN], q[MAXN]; // граф и все запросы
int dsu[MAXN], ancestor[MAXN];
bool u[MAXN];
int dsu_get (int v) {
return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]);
}
void dsu_unite (int a, int b, int new_ancestor) {
a = dsu_get (a), b = dsu_get (b);
if (rand() & 1) swap (a, b);
dsu[a] = b, ancestor[b] = new_ancestor;
}
void dfs (int v) {
dsu[v] = v, ancestor[v] = v;
u[v] = true;
for (size_t i=0; i<g[v].size(); ++i)
if (!u[g[v][i]]) {
dfs (g[v][i]);
dsu_unite (v, g[v][i], v);
}
for (size_t i=0; i<q[v].size(); ++i)
if (u[q[v][i]]) {
printf ("%d %d -> %d\n", v+1, q[v][i]+1,
ancestor[ dsu_get(q[v][i]) ]+1);
}
int main() {
... чтение графа ...
// чтение запросов
for (;;) {
int a, b = ...; // очередной запрос
--a, --b;
q[a].push_back (b);
q[b].push_back (a);
}
// обход в глубину и ответ на запросы
dfs (0);
}Java Lösung
Auto-Entwurf, vor dem Einreichen prüfenimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
const int MAXN = максимальное число вершин в графе;
ArrayList<Integer> g[MAXN], q[MAXN]; // граф и все запросы
int dsu[MAXN], ancestor[MAXN];
boolean u[MAXN];
int dsu_get (int v) {
return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]);
}
void dsu_unite (int a, int b, int new_ancestor) {
a = dsu_get (a), b = dsu_get (b);
if (rand() & 1) swap (a, b);
dsu[a] = b, ancestor[b] = new_ancestor;
}
void dfs (int v) {
dsu[v] = v, ancestor[v] = v;
u[v] = true;
for (size_t i=0; i<g[v].size(); ++i)
if (!u[g[v][i]]) {
dfs (g[v][i]);
dsu_unite (v, g[v][i], v);
}
for (size_t i=0; i<q[v].size(); ++i)
if (u[q[v][i]]) {
System.out.print ("%d %d -> %d\n", v+1, q[v][i]+1,
ancestor[ dsu_get(q[v][i]) ]+1);
}
int main() {
... чтение графа ...
// чтение запросов
for (;;) {
int a, b = ...; // очередной запрос
--a, --b;
q[a].push_back (b);
q[b].push_back (a);
}
// обход в глубину и ответ на запросы
dfs (0);
}
}Материал разбит как Algorithmusическая Aufgabe: изучить постановку, понять асимптотику и реализовать Algorithmus на выбранном языке.
Stellen zu dieser Aufgabe
aktive Stellen with overlapping task tags are angezeigt.