На досуге мне пришла интересная идея, которую я развил в алгоритм нахождения наименьшего общего предка(LCA) двух вершин в дереве. До появления этой идеи других алгоритмов для поиска LCA я не знал. Проверив корректность работы я поспешил изучить другие алгоритмы для решения этой задачи, но аналогичных моему я не нашел. Теперь поспешу поделиться им с сообществом.
Деревом называется неориентированный связный граф из N вершин и N-1 ребер. Из любой вершины до любой другой существует ровно один простой путь.
Корнем дерева будет называться такая вершина, от которой задано направление движения по дереву при его обходе.
Наименьшим общим предком двух вершин u и v будет называться такая вершина p, которая лежит на пути из корня и до вершины v, и до вершины u, а также максимально удаленная от него.
На вход поступает информация о дереве: N — количество вершин, N-1 пара вершин, которые соединены ребром и M — количество запросов. Далее программе поступают запросы: две вершины u и v, для которых требуется найти их наименьшего общего предка.
Будем хранить для каждой вершины расстояние до корня и предыдущую вершину(предка) из которой мы в нее пришли. Далее будем из вершин u и v подниматься к корню дерева. На каждом шаге будем выбирать вершину u или v ту, которая наиболее удалена от корня и далее вместо нее рассматривать уже ее предка, пока образуемые пути из начальных u и v не приведут в одну вершину — их наименьший общий предок. При разных вариантах дерева такой путь может состоять из N шагов, что при большом количестве вершин и запросов будет работать слишком медленно. Данная реализация требует O(N) времени на выполнение каждого запроса.
Теперь улучшим алгоритм. Для каждой вершины будем хранить расстояние до корня дерева dist, количество потомков у нее kids, а также предка(выбор которого будет определен ниже) из которого мы в нее пришли last и номер вершины, в которую из предка выходит ребро на пути в данную вершину turn.
Объявим необходимые переменные, для удобства это будет сделано в глобальной памяти.
Теперь для каждой вершины с помощью рекурсивной функции(вызов k_go(0)) посчитаем количество потомков у нее:
А теперь закончим подготовительную часть работы алгоритма и для каждой вершины заполним необходимую информацию. Вызываем функцию l_go(0, 0, 0, 1):
Теперь поясню как работает последняя часть кода, так как поиск количества потомков у вершины достаточно типичная задача.
Для каждой вершины мы смотрим ее потомков и из них выбираем такую вершину, у которой количество потомков максимально. Для нее вся информация о предке будет наследоваться от текущей, а меняться будет лишь расстояние до корня. Для всех остальных потомков этой вершины теперь предком last будет являться текущая вершина, а поворотом turn сам потомок.
Теперь я утверждаю, что если взять некоторую вершину a в дереве и пока из нее не придем в корень, то количество переходов к предку last не превысит двоичного логарифма от числа вершин в дереве.
Доказательство: пусть мы находимся в какой-то вершине v у которой есть один потомок. Тогда очевидно, что у потомка, выходящего из нее ссылка last на предка не изменится. В случае двух и более вершин мы получим одного потомка(у которого из всех потомков текущей вершине наибольшее число потомков) у кого ссылка унаследуется от текущей и всех остальных, у кого она обновится. Обозначим общее число потомков текущей вершины за N. Тогда из потомка этой вершины, у которой мы обновим ссылку на предка будет не более, чем N/2 потомков(иначе это число будет являться максимумом, но тогда обновление ссылки не требуется). Таким образом на каждой из вершин, которая является предком last для кого-то остается не более половины вершин, от всего исходящих из нее потомков. Итого длина такого пути не будет превышать двоичного логарифма от N.
Теперь перейдем к основной функции алгоритма и объяснения почему он работает.
Итак, имеем две вершины u и v, для которых надо узнать ответ на запрос. Вызовем функцию p = lca(u, v):
Функция рекурсивно поднимается в направлении корня. Для каждых последующих вершин a и b мы сначала проверяем вершину, в которую был произведен последний поворот. Если она совпадает — это означает, что либо вершина a лежит на пути к вершине b от корня, либо наоборот. В зависимости от того, какая вершина находится к корню ближе, та и является искомым наименьшим общим предком.
Иначе необходимо вершину a или b приблизить к корню. Приближать будем на основании того, какая из них в случае перехода к своему предку будет находиться дальше от корня(одна вершина будет постоянно стараться догнать вторую вершину на пути к корню). Таким образом рано или поздно вершины придут либо в одну вершину, которая сразу будет являться их наименьшим общим предком, либо одна из вершин будет лежать на пути из корня в другую вершину, что описано в первом шаге.
Для реализации алгоритма требуется O(N) памяти(всего памяти расходуется 6N), O(N) предварительный расчет и O(M * log(N)) времени для ответа на все запросы.
Алгоритм позволяет отвечать на запросы на заранее заданном дереве и отвечать на запросы сразу по мере их поступления за O(log(N)) на каждый.
Существует несколько алгоритмов решения этой задачи, каждый из которых отличается сложностью написания, временем на предварительный подсчет, ответ на запрос и размером требуемой памяти.
1) Ответ на запрос за O(log N), предварительный подсчет за O(N). Сложность реализации в необходимости использования структуры данных «дерево отрезков» или «sqrt-декомпозиции».
2) Метод двоичного подъема. Ответ на запрос за O(log N), предварительный подсчет за O(log N), используемая память(N * log(N)). Достаточно простая реализация с чуть лучшим временем работы, чем у приведенного мною алгоритма, но за счет дополнительно используемой памяти.
3) Алгоритм Фарах-Колтона и Бендера. Это самый оптимальный алгоритм, позволяет отвечать на запрос за O(1), но также требует много дополнительной памяти и отличается сложностью реализации.
А также алгоритм, который позволяют отвечать на запрос за O(1), но для этого необходимо знать информацию о всех запросах заранее.
4) Алгоритм Тарьяна
Таким образом представленный алгоритм в сложности реализации незначительно уступает чуть более быстрому алгоритму двоичного подъема, но требует меньше памяти и времени на предварительный подсчет. Хотелось бы услышать на этот счет мнение тех, кто знаком с алгоритмами решения этой задачи, чтобы оценить целесообразность его использования и уникальность. Спасибо всем, кто потратил время на понимание этой статьи.
UPD: Знающие люди подсказали мне, что мой алгоритм — это лишь одно из применений Heavy-Light декомпозиции. До этого я был не знаком с этой декомпозицией, но в любом случае приятно придумать что-то самому, пусть даже и существующее.
Введение
Деревом называется неориентированный связный граф из N вершин и N-1 ребер. Из любой вершины до любой другой существует ровно один простой путь.
Корнем дерева будет называться такая вершина, от которой задано направление движения по дереву при его обходе.
Наименьшим общим предком двух вершин u и v будет называться такая вершина p, которая лежит на пути из корня и до вершины v, и до вершины u, а также максимально удаленная от него.
Входные данные
На вход поступает информация о дереве: N — количество вершин, N-1 пара вершин, которые соединены ребром и M — количество запросов. Далее программе поступают запросы: две вершины u и v, для которых требуется найти их наименьшего общего предка.
Идея алгоритма
Будем хранить для каждой вершины расстояние до корня и предыдущую вершину(предка) из которой мы в нее пришли. Далее будем из вершин u и v подниматься к корню дерева. На каждом шаге будем выбирать вершину u или v ту, которая наиболее удалена от корня и далее вместо нее рассматривать уже ее предка, пока образуемые пути из начальных u и v не приведут в одну вершину — их наименьший общий предок. При разных вариантах дерева такой путь может состоять из N шагов, что при большом количестве вершин и запросов будет работать слишком медленно. Данная реализация требует O(N) времени на выполнение каждого запроса.
Теперь улучшим алгоритм. Для каждой вершины будем хранить расстояние до корня дерева dist, количество потомков у нее kids, а также предка(выбор которого будет определен ниже) из которого мы в нее пришли last и номер вершины, в которую из предка выходит ребро на пути в данную вершину turn.
Объявим необходимые переменные, для удобства это будет сделано в глобальной памяти.
const int SIZE = 100050;
vector<int> v[SIZE]; // список ребер для каждой вершины
bool vis[SIZE]; // пометки о посещении вершин при обходе
int kids[SIZE]; // кол-во потомков у каждой вершины
int dist[SIZE]; // расстояние от вершины до корня
int last[SIZE]; // номер предыдущей вершины
int turn[SIZE];
Теперь для каждой вершины с помощью рекурсивной функции(вызов k_go(0)) посчитаем количество потомков у нее:
int k_go(int s) {
int res = 0;
vis[s] = true;
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]])
res += k_go(v[s][i]) + 1;
}
kids[s] = res;
return res;
}
А теперь закончим подготовительную часть работы алгоритма и для каждой вершины заполним необходимую информацию. Вызываем функцию l_go(0, 0, 0, 1):
void l_go(int s, int d, int l, int r) {
vis[s] = true;
dist[s] = d;
last[s] = l;
turn[s] = r;
int maxval = 0;
int idx = -1;
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]]) {
int k = kids[v[s][i]];
if(k > maxval) idx = v[s][i], maxval = k;
}
}
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]]) {
if(idx == v[s][i])
l_go(v[s][i], d + 1, l, r);
else
l_go(v[s][i], d + 1, s, v[s][i]);
}
}
}
Теперь поясню как работает последняя часть кода, так как поиск количества потомков у вершины достаточно типичная задача.
Для каждой вершины мы смотрим ее потомков и из них выбираем такую вершину, у которой количество потомков максимально. Для нее вся информация о предке будет наследоваться от текущей, а меняться будет лишь расстояние до корня. Для всех остальных потомков этой вершины теперь предком last будет являться текущая вершина, а поворотом turn сам потомок.
Теперь я утверждаю, что если взять некоторую вершину a в дереве и пока из нее не придем в корень, то количество переходов к предку last не превысит двоичного логарифма от числа вершин в дереве.
Доказательство: пусть мы находимся в какой-то вершине v у которой есть один потомок. Тогда очевидно, что у потомка, выходящего из нее ссылка last на предка не изменится. В случае двух и более вершин мы получим одного потомка(у которого из всех потомков текущей вершине наибольшее число потомков) у кого ссылка унаследуется от текущей и всех остальных, у кого она обновится. Обозначим общее число потомков текущей вершины за N. Тогда из потомка этой вершины, у которой мы обновим ссылку на предка будет не более, чем N/2 потомков(иначе это число будет являться максимумом, но тогда обновление ссылки не требуется). Таким образом на каждой из вершин, которая является предком last для кого-то остается не более половины вершин, от всего исходящих из нее потомков. Итого длина такого пути не будет превышать двоичного логарифма от N.
Теперь перейдем к основной функции алгоритма и объяснения почему он работает.
Итак, имеем две вершины u и v, для которых надо узнать ответ на запрос. Вызовем функцию p = lca(u, v):
int lca(int a, int b) {
if(turn[a] == turn[b]) {
if(dist[a] < dist[b]) return a;
else return b;
}
if(dist[last[a]] > dist[last[b]]) return lca(last[a], b);
return lca(last[b], a);
}
Функция рекурсивно поднимается в направлении корня. Для каждых последующих вершин a и b мы сначала проверяем вершину, в которую был произведен последний поворот. Если она совпадает — это означает, что либо вершина a лежит на пути к вершине b от корня, либо наоборот. В зависимости от того, какая вершина находится к корню ближе, та и является искомым наименьшим общим предком.
Иначе необходимо вершину a или b приблизить к корню. Приближать будем на основании того, какая из них в случае перехода к своему предку будет находиться дальше от корня(одна вершина будет постоянно стараться догнать вторую вершину на пути к корню). Таким образом рано или поздно вершины придут либо в одну вершину, которая сразу будет являться их наименьшим общим предком, либо одна из вершин будет лежать на пути из корня в другую вершину, что описано в первом шаге.
Оценка работы алгоритма
Для реализации алгоритма требуется O(N) памяти(всего памяти расходуется 6N), O(N) предварительный расчет и O(M * log(N)) времени для ответа на все запросы.
Алгоритм позволяет отвечать на запросы на заранее заданном дереве и отвечать на запросы сразу по мере их поступления за O(log(N)) на каждый.
Эффективность других алгоритмов решения задачи поиска LCA
Существует несколько алгоритмов решения этой задачи, каждый из которых отличается сложностью написания, временем на предварительный подсчет, ответ на запрос и размером требуемой памяти.
1) Ответ на запрос за O(log N), предварительный подсчет за O(N). Сложность реализации в необходимости использования структуры данных «дерево отрезков» или «sqrt-декомпозиции».
2) Метод двоичного подъема. Ответ на запрос за O(log N), предварительный подсчет за O(log N), используемая память(N * log(N)). Достаточно простая реализация с чуть лучшим временем работы, чем у приведенного мною алгоритма, но за счет дополнительно используемой памяти.
3) Алгоритм Фарах-Колтона и Бендера. Это самый оптимальный алгоритм, позволяет отвечать на запрос за O(1), но также требует много дополнительной памяти и отличается сложностью реализации.
А также алгоритм, который позволяют отвечать на запрос за O(1), но для этого необходимо знать информацию о всех запросах заранее.
4) Алгоритм Тарьяна
Заключение
Таким образом представленный алгоритм в сложности реализации незначительно уступает чуть более быстрому алгоритму двоичного подъема, но требует меньше памяти и времени на предварительный подсчет. Хотелось бы услышать на этот счет мнение тех, кто знаком с алгоритмами решения этой задачи, чтобы оценить целесообразность его использования и уникальность. Спасибо всем, кто потратил время на понимание этой статьи.
UPD: Знающие люди подсказали мне, что мой алгоритм — это лишь одно из применений Heavy-Light декомпозиции. До этого я был не знаком с этой декомпозицией, но в любом случае приятно придумать что-то самому, пусть даже и существующее.