Наименьший общий предок. Нахождение за $O(1)$ в оффлайн (алгоритм Тарьяна)

Дано дерево $G$ с $n$ вершинами и дано $m$ запросов вида $(a_i, b_i)$ . Для каждого запроса $(a_i, b_i)$ требуется найти наименьшего общего предка вершин $a_i$ и $b_i$ , т.е. такую вершину $c_i$ , которая наиболее удалена от корня дерева, и при этом является предком обеих вершин $a_i$ и $b_i$ .

Мы рассматриваем задачу в режиме оффлайн, т.е. считая, что все запросы известны заранее. Описываемый ниже алгоритм позволяет ответить на все $m$ запросов за суммарное время $O(n+m)$ , т.е. при достаточно большом $m$ за $O(1)$ на запрос.

Алгоритм Тарьяна

Основой для алгоритма является структура данных "Система непересекающихся множеств", которая и была изобретена Тарьяном (Tarjan).

Алгоритм фактически представляет собой обход в глубину из корня дерева, в процессе которого постепенно находятся ответы на запросы. А именно, ответ на запрос $(v,u)$ находится, когда обход в глубину находится в вершине $u$ , а вершина $v$ уже была посещена, или наоборот.

Итак, пусть обход в глубину находится в вершине $v$ (и уже были выполнены переходы в её сыновей), и оказалось, что для какого-то запроса $(v,u)$ вершина $u$ уже была посещена обходом в глубину. Научимся тогда находить $\rm LCA$ этих двух вершин.

Заметим, что ${\rm LCA}(v,u)$ является либо самой вершиной $v$ , либо одним из её предков. Получается, нам надо найти самую нижнюю вершину среди предков $v$ (включая её саму), для которой вершина $u$ является потомком. Заметим, что при фиксированном $v$ по такому признаку (т.е. какой наименьший предок $v$ является и предком какой-то вершины) вершины дерева дерева распадаются на совокупность непересекающихся классов. Для каждого предка $p \not= v$ вершины $v$ её класс содержит саму эту вершину, а также все поддеревья с корнями в тех её сыновьях, которые лежат "слева" от пути до $v$ (т.е. которые были обработаны ранее, чем была достигнута $v$ ).

Нам надо научиться эффективно поддерживать все эти классы, для чего мы и применим структуру данных "Система непересекающихся множеств". Каждому классу будет соответствовать в этой структуре множество, причём для представителя этого множества мы определим величину $\rm ANCESTOR$ — ту вершину $p$ , которая и образует этот класс.

Рассмотрим подробно реализацию обхода в глубину. Пусть мы стоим в некоторой вершине $v$ . Поместим её в отдельный класс в структуре непересекающихся множеств, ${\rm ANCESTOR}[v] = v$ . Как обычно в обходе в глубину, перебираем все исходящие рёбра $(v, to)$ . Для каждого такого $to$ мы сначала должны вызвать обход в глубину из этой вершины, а потом добавить эту вершину со всем её поддеревом в класс вершины $v$ . Это реализуется операцией $\rm Union$ структуры данных "система непересекающихся множеств", с последующей установкой ${\rm ANCESTOR} = v$ для представителя множества (т.к. после объединения представитель класса мог измениться). Наконец, после обработки всех рёбер мы перебираем все запросы вида $(v,u)$ , и если $u$ была помечена как посещённая обходом в глубину, то ответом на этот запрос будет вершина ${\rm LCA}(v,u) = {\rm ANCESTOR}[{\rm FindSet}(u)]$ . Нетрудно заметить, что для каждого запроса это условие (что одна вершина запроса является текущей, а другая была посещена ранее) выполнится ровно один раз.

Оценим асимптотику. Она складывается из нескольких частей. Во-первых, это асимптотика обхода в глубину, которая в данном случае составляет $O(n)$ . Во-вторых, это операции по объединению множеств, которые в сумме для всех разумных $n$ затрачивают $O(n)$ операций. В-третьих, это для каждого запроса проверка условия (два раза на запрос) и определение результата (один раз на запрос), каждое, опять же, для всех разумных $n$ выполняется за $O(1)$ . Итоговая асимптотика получается $O(n+m)$ , что означает для достаточно больших $m$ ( $n = O(m)$ ) ответ за $O(1)$ на один запрос.

Реализация

Приведём полную реализацию данного алгоритма, включая слегка изменённую (с поддержкой $\rm ANCESTOR$ ) реализацию системы пересекающихся множеств (рандомизированный варианта).

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);
}

Наименьший общий предок. Нахождение за в оффлайн (алгоритм Тарьяна)

Алгоритм Тарьяна

Реализация

Наименьший общий предок. Нахождение за $O(1)$ в оффлайн (алгоритм Тарьяна)