Перегляд вихідного коду сторінки Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка

'''Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка'''&nbsp;— алгоритм для знаходження [[Найменший спільний предок|найменшого спільного предка]] пари вузлів у дереві. Він названий на честь [[Роберт Андре Тарджан|Роберта Андре Тарджана]], який відкрив цей алгоритм у 1979 році. Алгоритм Тарджана не є [[Онлайн алгоритм|алгоритмом реального часу]], тобто, він вимагає, щоб усі пари вузлів, для яких потрібно знайти найменший спільний предок, були вказані заздалегідь.

== Формальне визначення завдання ==
Дано [[Дерево (теорія графів)|дерево]] <math>G</math> з <math>n</math> вершинами і дано <math>m</math> запитів виду (<math>{a_i}</math>,<math>{b_i}</math>), потрібно для кожного запиту (<math>{a_i}</math>,<math>{b_i}</math>) знайти найменшого спільного предка, тобто, таку вершину <math>{c_i}</math>, яка найбільш віддалена від кореня дерева і при цьому є предком для обох вершин <math>{a_i}</math> та <math>{b_i}</math>.

== Алгоритм ==

=== Опис ===
Основою для алгоритму є структура даних «[[система неперетинних множин]]», яка і була винайдена [[Роберт Андре Тарджан|Тарджаном]].

Алгоритм фактично являє собою [[Пошук у глибину|обхід у глибину]] із кореня дерева, в процесі якого поступово знаходяться відповіді на запити. А саме, відповідь на запит знаходиться, коли обхід у глибину обробляє вершину <math>v</math>, а вершина <math>u</math> вже була відвідана, або навпаки.

Підвісимо наше дерево за будь-яку вершину, і запустимо обхід у глибину з неї. Нехай обхід дерева у глибину знаходиться в деякій вершині <math>v</math>. Помістимо її в окремий клас в структурі неперетинних множин, <math>ancestor[v]=v</math>. Як завжди, в обході у глибину, перебираємо усі вихідні ребра <math>(v,to)</math>. Для кожного такого <math>to</math> запускаємо обхід у глибину із цієї вершини, а потім додаємо цю вершину разом з її піддеревом в клас вершини <math>v</math>. Це реалізується операціями структури даних «система неперетинних множин», присвоюванням <math>ancestor = v</math> для представника множини (так як після об'єднання представник класу міг змінитися). Після обробки всіх ребер ми перебираємо всі запити виду <math>(v,u)</math>, і якщо вершина <math>u</math> була позначена як відвідана обходом у глибину, то відповіддю на цей запит буде вершина <math>LCA(v,u) = ancestor[FindSet(u)]</math>. Очевидно, що для кожного запиту ця умова (що одна вершина запиту оброблюється обходом у глибину, а друга була відвідана раніше) виповниться рівно один раз.

=== Псевдокод ===
Псевдокод нижче визначає найменший спільний предок для кожної пари із <math>P</math>, задано корінь дерева у якому діти вузла <math>n</math> зберігаються у множині <math>n.children</math>. Для цього алгоритму, множина <math>P</math> повинна бути вказана заздалегідь. В процедурі використовуються ''MakeSet'', ''Find'' та ''Union'' функції системи неперетинних множин. <math>MakeSet(u)</math> розміщує елемент <math>u</math> в нову множину, що складається з одного нього, <math>Find(u)</math> повертає представника множини, у якій міститься <math>u</math>, <math>Union(u,v)</math> створює нову множину, яка є об'єднанням множин, які містять <math>u</math> і <math>v</math>.

 '''function''' TarjanOLCA(u) '''is'''
     MakeSet(u)
     u.ancestor := u
     '''for each''' v '''in''' u.children '''do'''
         TarjanOLCA(v)
         Union(u, v)
         Find(u).ancestor := u
     u.color := black
     '''for each''' v '''such that''' {u, v} '''in''' P '''do'''
         '''if''' v.color == black '''then'''
             print "Tarjan's Lowest Common Ancestor of " + u +
                   " and " + v + " is " + Find(v).ancestor + "."

Нижче наведено оптимізовані версії функцій ''MakeSet'' , ''Union'' і ''Find''(використано [[Система неперетинних множин#Побудова ефективної структури даних|евристику стиснення шляху]] та [[Система неперетинних множин#Побудова ефективної структури даних|евристику об'єднання за рангом]](в наведеному нижче псевдокоді рангову евристику реалізовано на основі глибини дерев)).

 '''function''' MakeSet(x) '''is'''
     x.parent := x
     x.rank   := 1
  
 '''function''' Union(x, y) '''is'''
     xRoot := Find(x)
     yRoot := Find(y)
     '''if''' xRoot.rank > yRoot.rank '''then'''
         yRoot.parent := xRoot
     '''else if''' xRoot.rank < yRoot.rank '''then'''
         xRoot.parent := yRoot
     '''else if''' xRoot.rank == yRoot.rank '''then'''
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1
   
 '''function''' Find(x) '''is'''
     '''if''' x.parent != x '''then'''
        x.parent := Find(x.parent)
     '''return''' x.parent

=== Приклад реалізації мовою С++ ===
<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>

using namespace std;

const int N = 100001; // N - максимальна кількість вершин у дереві

vector < int > g[N], q[N];
int ancestor[N], parent[N], r[N];
bool visited[N];

void MakeSet(int x) {
	parent[x] = x;
	r[x] = 1;
}

int FindSet(int x ) {
	if (x == parent[x]) return x;
	return parent[x] = FindSet(parent[x]);
}

void Union(int x, int y) {
	int xRoot = FindSet(x), int yRoot = FindSet(y);

	if (r[xRoot] < r[yRoot])
		swap(xRoot, yRoot);

	parent[yRoot] = xRoot;
	r[xRoot] += r[yRoot];
}

void TarjanLCA(int v , int p) {
	MakeSet(v);
	ancestor[v] = v;
	for (int i = 0; i < g[v].size(); i++)
		if (g[v][i] != p ) {
			TarjanLCA(g[v][i] , v);
			Union(g[v][i], v);
			ancestor[FindSet(v)] = v; 
		}
	visited[v] = true;
	for (int i = 0; i < q[v].size(); i++)
		if (visited[q[v][i]])
			cout << "Tarjan's Lowest Common Ancestor of " << v << " and " << q[v][i] << " is " << ancestor[FindSet(q[v][i])] << '/n';
}

int main() {
	// Тут зчитуємо структуру графу та запити (звідки-небудь, наприклад, з файлу).

	TarjanLCA(1 , -1); //вважаємо , що коренем дерева є вершина під номером 1 
}
</syntaxhighlight>

=== Оцінка складності алгоритму ===
Оцінка складності алгоритму складається із декількох частин.

* Обхід у глибину виконується за <math>O(n)</math>.
* Операції по об'єднанню множин, які в сумі працюють за <math>O(n\alpha(n))</math> , де <math>\alpha(n)</math>&nbsp;— обернена [[функція Акермана]], яка зростає дуже повільно, настільки повільно, що для всіх розумних обмежень вона не перевершує 4 (приблизно для <math>n<=10^{600}</math>). Саме тому про асимптотику роботи системи неперетинних множин доречно говорити «майже константний час роботи»&nbsp;— <math>O(n)</math>. Кожний запит буде оброблений рівно один раз, тому можна вважати, що всі запити обробляються сумарно за <math>O(m)</math>.
* Для кожного запиту перевірка умови і визначення результату для всіх розумних <math>n</math> виконується за <math>O(1)</math>.

Отже, складність алгоритму&nbsp;— <math>O(n+m)</math>, що при достатньо великих <math>m</math> складає <math>O(1)</math> на один запит.

{{Портал|Програмування}}

== Література ==

* [https://e-maxx.ru/algo/lca_linear_offline Наименьший общий предок. Нахождение за O(1) в оффлайн (алгоритм Тарьяна)]{{ref-ru}}
* [https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Тарьяна_поиска_LCA_за_O(1)_в_оффлайн Алгоритм Тарьяна поиска LCA за O(1) в оффлайн] {{ref-ru}}
* [https://www.geeksforgeeks.org/tarjans-off-line-lowest-common-ancestors-algorithm Tarjan's off-line lowest common ancestors algorithm] {{ref-en}}
* {{citation
 | last1 = Gabow | first1 = H. N.
 | last2 = Tarjan | first2 = R. E.
 | authorlink2 = Роберт Андре Тарджан
 | contribution = A linear-time algorithm for a special case of disjoint set union
 | title = Proceedings of the 15th ACM Symposium on Theory of Computing (STOC)
 | year = 1983 | pages = 246–251 | doi = 10.1145/800061.808753}}.
* {{citation
 | last = Tarjan
 | first =R. E.
 | authorlink = Роберт Андре Тарджан
 | title = Applications of path compression on balanced trees
 | journal = [[Journal of the ACM]]
 | volume = 26
 | issue = 4
 | year = 1979
 | pages = 690–715
 | doi = 10.1145/322154.322161}}.

== Див. також ==
* [[Алгоритм Тар'яна]]
* [[Теорія графів]]
* [[Дерево (теорія графів)]]

{{Алгоритми на графах}}

[[Категорія:Алгоритми на графах]]
[[Категорія:Статті з прикладами коду мовою C++]]
[[Категорія:1979 у науці]]