E050. Lowest common ancestor. Нахождение за в оффлайн (算法 Тарьяна)
Источник: e-maxx.ru/algo, страница PDF 147.
given 树
с
vertexми и given
запросов вида
. Для каждого запроса
it is required
find наименьшего общего предка вершин
и
, т.е. такую вершину
, которая наиболее удалена от корня дерева,
и при этом является предком обеих вершин
и
. Мы рассматриваем задачу в режиме оффлайн, т.е. считая, что все запросы известны заранее. Описываемый
ниже 算法 позволяет ответить на все
запросов за суммарное время
, т.е. при достаточно
большом
за
на запрос.
算法 Тарьяна
Основой для 算法а является структура данных "Disjoint set union", которая и была изобретена Тарьяном (Tarjan). 算法 фактически представляет собой обход в глубину из корня дерева, в процессе которого постепенно
находятся ответы на запросы. А именно, ответ на запрос
находится, когда обход в глубину находится в вершине
, а vertex
уже была посещена, или наоборот.
Итак, пусть обход в глубину находится в вершине
(и уже были выполнены переходы в её сыновей), и оказалось, что
для какого-то запроса
vertex
уже была посещена обходом в глубину. Научимся тогда находить
этих двух вершин.
Заметим, что
является либо самой вершиной
, либо одним из её предков. Получается, нам надо
find самую нижнюю вершину среди предков
(включая её саму), для которой vertex
является потомком.
Заметим, что при фиксированном
по такому признаку (т.е. какой наименьший предок
является и предком какой-
то вершины) вершины дерева дерева распадаются на совокупность непересекающихся классов. Для каждого
предка
вершины
её класс содержит саму эту вершину, а также все поддеревья с корнями в тех её
сыновьях, которые лежат "слева" от пути до
(т.е. которые были обработаны ранее, чем была достигнута
). Нам надо научиться эффективно поддерживать все эти классы, для чего мы и применим структуру данных "Disjoint set union". Каждому классу будет соответствовать в этой структуре множество, причём
для представителя этого множества мы определим величину
— ту вершину
, которая и образует
этот класс. Рассмотрим подробно реализацию обхода в глубину. Пусть мы стоим в некоторой вершине
. Поместим её в
отдельный класс в структуре непересекающихся множеств,
. Как обычно в обходе в
глубину, перебираем все исходящие рёбра
. Для каждого такого
мы сначала должны вызвать обход в
глубину из этой вершины, а потом добавить эту вершину со всем её под树м в класс вершины
. Это
реализуется операцией
структуры данных "Disjoint set union", с последующей
установкой
для представителя множества (т.к. после объединения представитель класса мог измениться). Наконец, после обработки всех рёбер мы перебираем все запросы вида
, и если
была
помечена как посещённая обходом в глубину, то ответом на этот запрос будет
vertex
. Нетрудно заметить, что для каждого запроса
это 题意 (что одна vertex запроса является текущей, а другая была посещена ранее) выполнится ровно один раз. Оценим асимптотику. Она складывается из нескольких частей. Во-первых, это Asymptotic complexity обхода в
глубину, которая в данном случае составляет
. Во-вторых, это операции по объединению множеств, которые
в сумме для всех разумных
затрачивают
операций. В-третьих, это для каждого запроса проверка условия
(два раза на запрос) и 定义 результата (один раз на запрос), каждое, опять же, для всех разумных
выполняется за
. Итоговая Asymptotic complexity получается
, что означает для достаточно больших
(
) ответ за
на один запрос.
实现
Приведём полную реализацию данного 算法а, включая слегка изменённую (с поддержкой ) реализацию системы пересекающихся множеств (рандомизированный варианта).
const int MAXN = максимальное number вершин в 图е;
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);
}
C# 解法
自动草稿，提交前请检查using 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++ 解法
匹配/原始const 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 解法
自动草稿，提交前请检查import 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);
}
}Материал разбит как 算法ическая 题目: изучить постановку, понять асимптотику и реализовать 算法 на выбранном языке.
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.