Крайне любопытная структура данных, на основе которой можно организовать приоритетную очередь.
Ниже представлена асимптотическая сложность базовых операций:
1. Добавление нового элемента O(1)
2. Определение минимального элемента O(1)
3. Слияние двух фибоначчиевых куч O(1)
4. Удаление минимального элемента O(logN)
5. Изменение приоритета элемента O(logN)
Фибоначчиева куча представляет собой набор фибоначчиевых деревьев.
Фибоначчиево дерево представляют собой k-ричное дерево для которого существует только одно правило: сын не должен превышать своего отца.
Братья-узлы объединены в кольцевой список. Поэтому отцу не обязательно знать всех сыновей. Достаточно иметь ссылочку на одного из них. Минимальный элемент всей кучи – это корень одного из деревьев. Ниже представлен пример фибоначчиевой кучи.
Программно будем хранить узел фибоначчиева дерева и саму фибоначчиеву кучу так:
typedef bool (*cmpPtr)(node*, node*);
struct node {
node* parent; // указатель на отца
node* child; // указатель на одного из сыновей
node* left; // указатель на левого брата
node* right; // указатель на правого брата
int degree; // количество дочерних узлов
bool mark; // метка - был ли удален один из дочерних элементов
int key; // числовое значение узла
};
struct fib_heap {
node* min; // узел с минимальным корнем
int roots_amount; // количество узлов
cmpPtr less; // указатель на функцию-компаратор
}
* This source code was highlighted with Source Code Highlighter.
Рассмотрим работу алгоритма на конкретном примере. Последовательно будет добавлять элементы из массива:
{5,1,3,2,4,0,7,6}
1. Добавление элемента
В начальный момент куча пуста и нет ни одного дерева. Новый элемент “5” становится корнем единственного дерева и одновременно минимальным элементом всей кучи.
Элемент “1” образует новое дерево и отбирает титул минимального элемента кучи у “5”. Каждый новый добавленный элемент будет образовывать новую дерево, а его корень будет добавляться в кольцевой список корней.
Элемент “3” добавляется справа от минимального элемента.
Элемент “2” не меняет минимальный элемент кучи и как и элемент “3” встает справа от минимального корня.
Элемент “1” повторяет судьбу “2”
Элемент “0” становится новым минимальным элементом кучи и также добавляется справа от предыдущего минимального элемента
Программно функция добавления нового элемента может выглядеть так:
void add(node* Node, node** bro, node* par = NULL) {
if (*bro == NULL) {
*bro = Node;
Node->left = Node;
Node->right = Node;
}
else {
Node->right = (*bro)->right;
Node->right->left = Node;
Node->left = *bro;
(*bro)->right = Node;
}
if (less(Node, *bro))
*bro = Node;
if(*bro == min) {
roots_amount++;
Node->parent = NULL;
}
if (par){
par->degree++;
Node->parent = par;
}
}
node* add(int key) {
node* Node = new node(key);
add(Node,&min);
return Node;
}
* This source code was highlighted with Source Code Highlighter.
2. Определение минимального элемента
Указатель на минимальный элемент кучи хранится в специальном поле. Доступ к нему осуществляется за O(1)
3. Объединение двух фибоначчиевых куч
То, что эта функция работает за константное время выгодно отличает фибоначчиеву кучу от биномиальной и двоичной, где время работы пропорционально O(logN) и O(NlogN).
Т.к. корневые узлы объединены в циклический список, то для объединения двух куч необходимо объединить два циклических списка корней в один. Это можно сделать за константное время путем аккуратного перекидывания ссылок:
struct fib_heap {
void union_fib_heap(fib_heap &fb) {
union_root(fb.min,fb.roots_amount);
if (!min || (fb.min && less(fb.min, min)))
min = fb.min;
fb.clear();
}
void union_root(node* Node, int nodes_amount) {
if (Node == NULL) return;
if (min == NULL) {
min = Node;
roots_amount = nodes_amount;
}
else {
node *L = Node->left;
node *R = min->right;
min->right = Node;
Node->left = min;
L->right = R;
R->left = L;
roots_amount += nodes_amount;
}
}
};
int main() {
fib_heap fh1,fh2;
...
fh1.union_fib_heap(fh2);
...
}
* This source code was highlighted with Source Code Highlighter.
4. Удаление минимального элемента
Эта операция является наиболее трудоемкой. Поэтому ее описание разобьем на несколько этапов:
4.1. Если минимальный элемент имеет детей, то их необходимо сделать корневыми узлами. В этом может помочь функция union_root, рассмотренная ранее. Этот момент будет проиллюстрирован чуть позже.
4.2. Удаляем минимальный элемент из кольцевого списка корней. Для этого нужно грамотно перебросить ссылочки с левого и правого брата. При этом новым минимальным элементом кучи на время становится правый брат удаляемого элемента. Не факт, что правый брат является минимальным узлом, но после окончания функции будет найден корректный минимальный узел. Может возникнуть такая ситуация, что удаляемый элемент является последним элементов в кольцевом списке. Этот случай наступит, когда min->right == min и его нужно обработать отдельно. В случае, когда удаляемый элемент не является последним, то нужно выполнить процесс уплотнения кучи(consolidate):
int extract_min() {
node* res = min;
if (res) {
childs_in_root(res);
remove_root(res);
if (res->right == res)
min = 0;
else {
min = min->right;
consolidate();
}
}
int ans = res ? res->key : ERROR;
delete res;
return ans;
}
* This source code was highlighted with Source Code Highlighter.
4.3. Процесс уплотнения кучи(consolidate) лучше понять на иллюстрации кучи, которую мы получили на этапе процесса добавления новых элементов. На каждом шаге будут формироваться новые фибоначчиевы деревья размером равным степени двойки. Если на каком-то этапе получается два дерева одинакового размера они объединяются в одно и так повторяется до тех пор пока в наборе остаются деревья одинакового размера.
В итоге получаются 3 дерева уникального размера. Все корни циклического списка, который был вначале обработаны. На этом шаге процесс уплотнения кучи закончен. Отметим, что на текущем шаге уже известен минимальный корень кучи. Он определяется каждый раз, когда образуется дерево уникального размера.
После удаления минимального элемента “1” текущим элементом становится правый его брат “6”, образую первое фибоначчиево дерево размером 1.
Переходим к правому брату элемента “6”, т.к. к “7”, который образует дерево размером 1. Но на предыдущем шаге уже было получено дерево с таким размером. Объединяем их
При слиянии двух деревьев “6” и “7” минимальный корень двух деревьев становится общим корнем. А корень второго дерева становится сыном общего корня. После чего образуется новое дерево размером 2 – “6-7”. Увеличиваем счетчик детей у элемента “2”.
Следующим элементом становится “4”, образуя дерево размером 1. На текущем шаге имеется одно дерево размером 2 и одно дерево размером 1. Поэтому сливать деревья не надо
Новое дерево “2” имеет тот же размер, что и дерево “4”. Сливаем их.
После слияния получается дерево “2-4” размером 2. Но у нас уже есть дерево размером 2 – “6-7”. Поэтому сливаем сливаем эти деревья
При слиянии деревьев на предыдущем шаге образуется дерево размером 4, корнем которого является элемент “2”. Элемент “6” становится сыном элемента “2”. На рисунке нет явной связи “2” и “6”, потому что “6” включена в циклический список с “4”, который является сыном “2”.
Новый дерево “3” имеет уникальную размерность
Далее рассуждения можно продолжить по аналогии с предыдущими шагами.
Давайте теперь более детально разберем, что происходит в п. 4.1 и 4.2. Допустим, что на текущий момент уже удален минимальный элемент “1” и мы имеем:
Минимальным элементом кучи является 2.
В п.4.1. сказано, что нужно детей минимального элемента поместить в корневой список кучи, что мы и делаем. Далее элемент “2” удаляется и происходит сжатие кучи по вышеописанной схеме.
5. Изменение приоритета элемента
Осталась последняя операция, которую мы разберем. Очевидно, если новый приоритет элемента не ниже, чем приоритет его отца, то ничего делать не нужно. В противном случае действует по следующей схеме:
5.1. Удаляем текущий элемент A из кольцевого списка братьев и если отец A(P) ссылался на этот элемент A, то перебрасываем ссылку child элемента P на правого брата A. Уменьшаем счетчик количества сыновей у P и делаем метку mark равную true. Это означет, что у элемента P был удален сын. Данная метка указывает на то, что если возникнет такая ситуация, что у одного узла будет удалено более одного сына, то его нужно поместить в кольцевой список корней.
5.2 Добавляем элемент A в кольцевой список корней. Если приоритет элемента A меньше минимального корня, то элемент A становится минимальным элементом кучи.
5.3. Делаем каскадное вырезание. То, о чем идет речь в п.5.1. Если у отца элемента A – элемента P ранее удалялся сын, то необходимо выполнить поместить элемент P в кольцевой список корней. Далее продолжить п.5.3. для отца элемента P, если у него также ранее удалялись сыновья.
Задача: EZDIJKST
Решение: здесь
Примечание: полная реализация фибоначчиевой кучи
Автор: Беляев Игорь на 21:22 0 коммент. Ссылки на это сообщение
понедельник, 31 октября 2011 г.
Занятие №9 (Методы тестирования задач)
[Все занятия]
Практика: [Официальная страница]
Учебные задачи:
Задача A.
[Тестирование целых точек отрезка]
В тесте нет ничего сверхъестественного. Особое внимание нужно уделить случаю, когда точки лежат на прямой, параллельной одной из осей.
Задача B.
[Тестирование сортировки] [Генератор тестов]
С этой задачей я промучился очень долго. Я даже готовил слезный пост, с мольбами о помощи, в котором описал свои рассуждения по поводу этой задачи. Но так получилось, что когда был готов генератор тестов, первый же им сгенерированный набор зашел на OK. Приведу основной фрагмент того слезного поста:
” Какие тесты будем делать?
1) Генерируем рандомные числа во всем диапазоне. Размер массива немаксимален.
2) Все тоже самое, но размер массива максимален.
3) Упорядоченный массив. Лучше захватить и отрицательные и положительные числа
4) Обратный массив по аналогии с 3 тестом.
5) Массив из одного элемента(пускай отрицательного). Проверка на потенциальные Run-time errors.
6) Массив из двух элементов (отрицательного и положительного)
7) Массив не максимальной длины, который представляет собой кучу.
8) Массив с одинаковыми элементами. В том числе и по модулю. Так чтобы положительные числа были перед отрицательными.
9) Массив с одинаковыми элементами. Неотрицательными
10) Массив с одинаковыми элементами. Неположительными”.
Олимпиадные задачи:
Задача A.
[Распаковка строчки]
Задача для начинающих на аккуратную реализацию.
Задача B.
[Сортировка масс]
Нужно быть внимательным в выборе типов данных.
Задача C.
[Результаты олимпиады]
Несложная задача, но условие наводит ужас обилием различных вариантов проверок. На практике все оказалось не так страшно: само решение занимает меньше места чем ввод данных =)
Дополнительные олимпиадные задачи:
Задача A.
[Проверьте правильность ситуации]
С первого взгляда задача кажется несложной. Но нужно быть внимательным и аккуратным.
Задача B.
[Гражданская оборона]
Задача на умение писать компараторы. Удобно использовать граничные элементы, чтобы избежать лишние проверки.
Задача C.
[Переключение между окнами]
Задача на умение пользоваться списком и выполнять операции удаления элемента и вставки его в конец. Пришлось повозиться со случаем, когда имя программы представляет пробельные символы.
Автор: Беляев Игорь на 21:12 0 коммент. Ссылки на это сообщение
Алгоритм Кнута-Морриса-Пратта
По мотивам лекции Сагунова Данила и реализации indy256
Алгоритм относится к разряду алгоритмов поиска подстроки в строке.
Префиксом строки S называется подстрока строки S, первый символ которой совпадает с первым символом строки S.
Суффиксом строки S называется подстрока строки S, последний символ которой совпадает с последним символом строки S.
Длина префикса и суффикса строки S строго меньше длины строки S.
Префикс функция от строки S: П(S) – это максимальная длина префикса S, совпадающего с её суффиксом.
Z-функция от строки S – это массив длинной равной длине строки S, где Z[i] – это префикс функция от подстроки S, последний символ, которой равен S[i].
Пусть S = “abababaaabababac”
z[0] = П(“a”) = 0
z[1] = П(“ab”) = 0
z[2] = П(“aba”) = 1
z[3] = П(“abab”) = 2
z[4] = П(“ababa”) = 3
z[5] = П(“ababab”) = 4
z[6] = П(“abababa”) = 5
z[7] = П(“abababaa”) = 1
z[8] = П(“abababaaa”) = 1
z[9] = П(“abababaaab”) = 2
z[10] = П(“abababaaaba”) = 3
z[11] = П(“abababaaabab”) = 4
z[12] = П(“abababaaababa”) = 5
z[13] = П(“abababaaababab”) = 6
z[14] = П(“abababaaabababa”) = 7
z[15] = П(“abababaaabababac”) = 0
Можно заметить, что z-функция может увеличиваться за один шаг не более чем на 1, а уменьшиться на произвольное количество.
void prefix_func(const string &str, vector &z) {
z.resize(str.size());
z[0] = 0;
for (int i=1;i int pos = z[i-1];
while (pos > 0 && str[pos] != str[i])
pos = z[pos-1];
z[i] = pos + (str[pos] == str[i] ? 1 : 0);
}
}
* This source code was highlighted with Source Code Highlighter.
Ключевым моментов в функции подсчета Z-функции является цикл while(7-8 строки). На каждом шаге пытаемся увеличить длину префикса, равного суффиксу. Если это сделать не удается, то необходимо уменьшить размер префикса максимальным образом.
Рассмотрим нахождение z[7]. Текущая подстрока “abababaa”, z[6] = 5.
На шаге 7 пытаемся продолжить увеличивать длину префикса.
1) Сравниваем 5-ый символ с последним: ”abababaa”
2) Необходимо максимальным образом уменьшить длину префикса. Для этого нужно найти префикс префикса, который обязательно будет равен суффиксу суффикса. П(”ababa”) = 3
3) Сравниваем 3-ый символ с последним: “abababaa”. Продолжаем рассуждения пока префикс существует, т.е. пока имеет ненулевую длину, либо до совпадения концов префикса и суффикса. П(“aba”) = 1.
4) Сравниваем 1-ый символ с последним: “abababaa”. П(“a”) = 0.
5) Сравниваем 0-ой символ с последним: “abababaa”. Успех =)
Значит z[7] = 1.
Вернемся к исходной задаче поиска подстроки(S) в строке(TEXT). Если не хочется заморачиваться, а главное если есть такая возможность, то в общем случае можно получить строку TEXT’ = S + sep + TEXT, где sep – это символ, который гарантированно не встречается в строках S и TEXT, а “+” – это конкатенация строк. Затем найти z-функцию от TEXT’. Если z[i] = длина(S), значит S является подстрокой строки TEXT.
void kmp() {
text = str + "#" + text;
z.resize(text.size(), -1);
z[0] = 0;
for (int i=1;i int pos = z[i-1];
while (pos != -1 && text[i] != text[pos])
pos = pos - 1 >= 0 ? z[pos-1] : -1;
z[i] = pos + 1;
}
}
void output() {
for (int i=0;i if (z[i] == str.size()) {
cout<< i - 2*str.size() <<' ';
}
}
}
* This source code was highlighted with Source Code Highlighter.
Понятно, что в данной реализации происходит лишнее выделение памяти, и не всегда есть возможность вести себя так вальяжно.
Более эффективная реализация:
void prefix_func(const string &str, vector &z) {
z.resize(str.size());
z[0] = 0;
for (int i=1;i int pos = z[i-1];
while (pos > 0 && str[pos] != str[i])
pos = z[pos-1];
z[i] = pos + (str[pos] == str[i] ? 1 : 0);
}
}
void kmp(const string &text, const string &str) {
vector z;
prefix_func(str,z);
int pos = 0;
for (int i=0; i while (pos > 0 && (pos >= str.size() || str[pos] != text[i]) )
pos = z[pos-1];
if (text[i] == str[pos]) pos++;
if (pos == str.size())
printf("%d ", i - pos + 1);
}
}
* This source code was highlighted with Source Code Highlighter.
Здесь сначала считается z-функция для строки S, а потом происходит эмуляция первой реализации, как будто строка S является префиксом строки TEXT. Как видно в данном случае затраты на память сократятся.
Попрактиковаться можно здесь:
spoj.pl - NHAY
acmp.ru – Поиск подстроки
Автор: Беляев Игорь на 8:58 1 коммент. Ссылки на это сообщение
воскресенье, 23 октября 2011 г.
Занятие №8. Динамическое программирование с двумя и более параметрами
Теория: Лекция [Все занятия]
Практика: [Официальная страница]
Учебные задачи:
Задача A.
[Наибольшая общая подпоследовательность (НОП)]
В данной задаче можно применить классический алгоритм Нудельмана-Вунша.
Задача B.
[Наибольшая общая подпоследовательность с восстановлением ответа]
Продолжение предыдущей задачи с той разницей, что в текущей реализации использовались барьерные первый столбец и строка.
Задача C.
[Биномиальные коэффициенты]
Наверное последняя проходная задача на ДП в этом цикле. Суть задачи сводиться к классической черепашке.
Олимпиадные задачи:
Задача A.
[Движение по полосам]
Очень хорошая задача. Решаем ДП с двумя параметрами: количество использованных полос(s), количество использованных дорог(r). Ответом на вопрос будет являться значение dp(n,m), где n – общее количество полос, m – общее количество дорог. Чтобы найти значение на текущем шаге dp(s,r), необходимо перебрать и сложить все возможные значения dp(s-1,r’).
Задача B.
[Еловая аллея]
Данная реализация отражает идею, предложенную в разборе, но имеет сложность M*M*N.
Задача C.
[Почти палиндром]
Классическая LR динамика. Нужно быть осторожным в выборе типа данных для элементов таблицы.
Дополнительные олимпиадные задачи:
Задача A.
[Электронная почта]
Суть задачи сводится к поиску оптимальной стратегии в игре Zuma, с одним только отличием, что нет минимального количества рядом стоящих шариков, которые могут быть удалены за один раз. В обычной игре это число равно 3. На spoj.pl есть задача ZUMA, в которой как раз фигурирует это минимальное значение рядом стоящих шариков.
Решать будем двумерной LR динамикой. В таблице dp[i][j] находится оптимальный ответ для подмассива с i-ого по j-ый элементы. Базой динамики будут служить два факта:
1) if (i > j) dp[i][j] = 0
2) if (i == j) dp[i][j] = 1
Теперь рассмотрим общий случай для произвольных i и j:
I) Очевидно, что может быть такая ситуация, когда исходный массив можно разбить на набор непересекающихся подмассивов и последовательно избавиться от каждого из них. Например для массива A = {1, 2, 2, 3, 4, 5, 5, 5} это будет оптимальная стратегия. Этот случай обрабатывается в строках 40-41.
II) Отдельно стоит рассмотреть случай, когда элементы a[i] и a[j] равны. Возможно стоит сначала избавиться от подмассива [i+1, j-1], а потом за одну итерацию убрать крайние элементы за одну итерацию. Например для массива B = {1,,2,3,4,5,5,5,4,3,2,1} это будет оптимальная стратегия. Этот случай обрабатывается в строке 44.
III) Продолжим рассматривать случай, когда граничные элементы подмассива равны. Может возникнуть такая ситуация, когда есть элемент a[i] == a[k] == a[j], причем i < k < j. При этом выгодно сначала избавиться от подмассива [i+1,k-1], чтобы элементы a[i] и a[k] встали рядышком, либо же избавиться от подмассива [k+1,j-1], чтобы рядом оказались элементы a[k] и a[j]. Например для массива С = {1,2,3,4,3,2,1,5,6,7,6,5,1} оптимальной стратегия будет III с элементами II(для удаления подмассивов межды единицами). Этот момент обрабатывается в строках 45-49.
Задача B.
[Плитки]
Шикарная задача на динамику по рванному краю(динамика по профилю).
Будем заполнять таблицу dp[clr][len][mask], где clr – цвет, на который заканчивается последовательность длины len, удовлетворяющая битовой маске mask. Разберемся с битовой маской.
Сразу оговоримся, что предложенное решение использует маску, ориентированную на несимметричную матрицу цветов. Условно обозначим 3 возможных цвета как R,G и B. Тогда имеем матрицу:
R G B
R 0 1 2
G 3 4 5
B 6 7 8
На пересечении цветов указано значение row * 3 + col, где row – номер строки, col – номер столбца. Получаем следующий массив:
8 7 6 5 4 3 2 1 0 - номер сочетания цветов
BB BG BR GB GG GR RB RG RR - сочетание цветов
Пусть номер сочетания цветов указывает на бит в маске.
Зафиксируем для таблицы dp значение clr, len и mask. Номер единичного бита в mask говорит о том, что сочетание цветов, соответствующего номеру бита уже было в конце строки в диапазоне [len,n-1].
Отсюда можно получить базу динамики. Перебрав все пары цветов c1 и с2, в случае валидной комбинации c1-c2 dp[c1][n-2][code(c1,c2)] = 1. Случай, когда длина строки равна 1 можно рассмотреть отдельно.
Подсчет всех остальных значений отображен в строках 104-120:
Для фиксированных c1, c2, len, mask можно однозначно определить ответ:
dp[c1][len][mask] = dp[c2][len+1][mask] + dp[c2][len+1][mask ^ cur_mask], где cur_mask – закодированная комбинация цветов c1 и с2. Говоря другими словами последовательность, заканчивающаяся цветом c1 длины len и маской mask могла получиться из строки, заканчивающейся цветом c2, длины len+1 с той же маской, а также маской, в которой ранее не использовалось сочетание цветов c1 и с2.
Ответ формируется из элементов dp[c][0][mask], где с принимает все возможные значения цветов, а mask принимает все возможные валидные комбинации цветов, содержащие всю матрицу цветов.
Задача C.
[Симпатичные узоры возвращаются]
Задача является логическим продолжением задачи Симпатичные узоры, которое наверное является классикой динамики по рваному контуру. Ее разбор дан в лекции. Здесь лежит мое решение.
Исходная задача также разобрана в лекции. Суть ее сводится к быстрому перемножению матриц. Данный подход использовался в алгоритме для нахождения достижимости за k шагов произвольной вершины j из произвольной вершины i. Там нужно было возвести исходную матрицу смежности в степень k.
Автор: Беляев Игорь на 17:54 0 коммент. Ссылки на это сообщение
четверг, 20 октября 2011 г.
Система непересекающихся множеств (Disjoint set union)
Если мы работаем с объектами, которые во время работы могут объединяться в группы. Причем эти группы попарно не имеют общих элемент(непересекающиеся множества). То скорее всего нам пригодится структура данных “Система непересекающихся множеств” (DSU). С помощью нее можно сделать две операции:
1) int find_set(X) - определение множества, в котором находится элемент X. При этом множество определяется одним(лидирующим) элементом.
2) void union_set(X,Y) - объединение множества, в котором находится элемент X с множеством, в котором находится элемент Y.
Полный обзор этой темы можно найти на емаксе.
Множества будут представлены в виде леса(набор деревьев), т.е. каждое множество будет являться деревом. При этом для каждого элемента будет храниться его предок. Это проще всего сделать с помощью массива parent. В начальный момент времени каждый элемент будет являться предком для самого себя, т.е. каждое дерево состоит из одного элемента.
void init() {
for (int i=1;i<=n;i++)
parent[i] = i;
}
* This source code was highlighted with Source Code Highlighter.
Теперь давайте подумаем как можно реализовать функцию find_set. В качестве лидирующего элемента нужно брать корневой элемент дерева, т.к. только он является общим для всех элементов дерева. В самой простой реализации можно последовательно добраться из текущей вершины до корневой за линейное время. Отметим тот факт, что с большой вероятностью придется проделывать этот путь много раз, поэтому сразу появляется первая эвристика. Можно один раз определить корневой узел для текущей вершины и назначить его родителем. Тоже самое нужно проделать для каждой вершины, которая встречается на пути от текущей вершины до корневой.
int find_set(int x) {
if (parent[x] == x)
return x;
return parent[x] = find_set(parent[x]);
}
* This source code was highlighted with Source Code Highlighter.
Теперь давайте рассмотрим операцию объединения двух множеств. При объединении двух множеств выбирается один лидирующий элемент. Очевидно, что он должен быть лидирующим элементов одного из объединяемых множеств. Какое же множество выбрать? Нужно меньшее множество присоединять к большему. Это целесообразно, потому что придется переопределять нового предка для меньшего количества элементов.
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if(x != y) {
if (size[x] < size[y])
swap(x,y);
parent[y] = x;
size[x] += size[y];
}
}
* This source code was highlighted with Source Code Highlighter.
Как видно был заведен еще один массив size, в котором на [i] месте хранится количество элементов в дереве, корнем которого является элемент [i]. Но можно обойтись без дополнительного массива подружившись с рандомом.
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if (rand()&1)
parent[x] = y;
else
parent[y] = x;
}
* This source code was highlighted with Source Code Highlighter.
Как показывает практика существенных замедлений такое решение не дает.
Существенным минусом DSU является то, что нельзя одно множество разбить на два. Но даже несмотря на это у DSU целый паровоз применений (см. емакс)
Для закрепления материала предлагаю решить две несложные задачи:
1) [Острова] (DSU в чистом виде) [Решение]
2) [Паутина Ананси] [Решение]
Ниже представлена асимптотическая сложность базовых операций:
1. Добавление нового элемента O(1)
2. Определение минимального элемента O(1)
3. Слияние двух фибоначчиевых куч O(1)
4. Удаление минимального элемента O(logN)
5. Изменение приоритета элемента O(logN)
Фибоначчиева куча представляет собой набор фибоначчиевых деревьев.
Фибоначчиево дерево представляют собой k-ричное дерево для которого существует только одно правило: сын не должен превышать своего отца.
Братья-узлы объединены в кольцевой список. Поэтому отцу не обязательно знать всех сыновей. Достаточно иметь ссылочку на одного из них. Минимальный элемент всей кучи – это корень одного из деревьев. Ниже представлен пример фибоначчиевой кучи.
Программно будем хранить узел фибоначчиева дерева и саму фибоначчиеву кучу так:
typedef bool (*cmpPtr)(node*, node*);
struct node {
node* parent; // указатель на отца
node* child; // указатель на одного из сыновей
node* left; // указатель на левого брата
node* right; // указатель на правого брата
int degree; // количество дочерних узлов
bool mark; // метка - был ли удален один из дочерних элементов
int key; // числовое значение узла
};
struct fib_heap {
node* min; // узел с минимальным корнем
int roots_amount; // количество узлов
cmpPtr less; // указатель на функцию-компаратор
}
* This source code was highlighted with Source Code Highlighter.
Рассмотрим работу алгоритма на конкретном примере. Последовательно будет добавлять элементы из массива:
{5,1,3,2,4,0,7,6}
1. Добавление элемента
В начальный момент куча пуста и нет ни одного дерева. Новый элемент “5” становится корнем единственного дерева и одновременно минимальным элементом всей кучи.
Элемент “1” образует новое дерево и отбирает титул минимального элемента кучи у “5”. Каждый новый добавленный элемент будет образовывать новую дерево, а его корень будет добавляться в кольцевой список корней.
Элемент “3” добавляется справа от минимального элемента.
Элемент “2” не меняет минимальный элемент кучи и как и элемент “3” встает справа от минимального корня.
Элемент “1” повторяет судьбу “2”
Элемент “0” становится новым минимальным элементом кучи и также добавляется справа от предыдущего минимального элемента
Программно функция добавления нового элемента может выглядеть так:
void add(node* Node, node** bro, node* par = NULL) {
if (*bro == NULL) {
*bro = Node;
Node->left = Node;
Node->right = Node;
}
else {
Node->right = (*bro)->right;
Node->right->left = Node;
Node->left = *bro;
(*bro)->right = Node;
}
if (less(Node, *bro))
*bro = Node;
if(*bro == min) {
roots_amount++;
Node->parent = NULL;
}
if (par){
par->degree++;
Node->parent = par;
}
}
node* add(int key) {
node* Node = new node(key);
add(Node,&min);
return Node;
}
* This source code was highlighted with Source Code Highlighter.
2. Определение минимального элемента
Указатель на минимальный элемент кучи хранится в специальном поле. Доступ к нему осуществляется за O(1)
3. Объединение двух фибоначчиевых куч
То, что эта функция работает за константное время выгодно отличает фибоначчиеву кучу от биномиальной и двоичной, где время работы пропорционально O(logN) и O(NlogN).
Т.к. корневые узлы объединены в циклический список, то для объединения двух куч необходимо объединить два циклических списка корней в один. Это можно сделать за константное время путем аккуратного перекидывания ссылок:
struct fib_heap {
void union_fib_heap(fib_heap &fb) {
union_root(fb.min,fb.roots_amount);
if (!min || (fb.min && less(fb.min, min)))
min = fb.min;
fb.clear();
}
void union_root(node* Node, int nodes_amount) {
if (Node == NULL) return;
if (min == NULL) {
min = Node;
roots_amount = nodes_amount;
}
else {
node *L = Node->left;
node *R = min->right;
min->right = Node;
Node->left = min;
L->right = R;
R->left = L;
roots_amount += nodes_amount;
}
}
};
int main() {
fib_heap fh1,fh2;
...
fh1.union_fib_heap(fh2);
...
}
* This source code was highlighted with Source Code Highlighter.
4. Удаление минимального элемента
Эта операция является наиболее трудоемкой. Поэтому ее описание разобьем на несколько этапов:
4.1. Если минимальный элемент имеет детей, то их необходимо сделать корневыми узлами. В этом может помочь функция union_root, рассмотренная ранее. Этот момент будет проиллюстрирован чуть позже.
4.2. Удаляем минимальный элемент из кольцевого списка корней. Для этого нужно грамотно перебросить ссылочки с левого и правого брата. При этом новым минимальным элементом кучи на время становится правый брат удаляемого элемента. Не факт, что правый брат является минимальным узлом, но после окончания функции будет найден корректный минимальный узел. Может возникнуть такая ситуация, что удаляемый элемент является последним элементов в кольцевом списке. Этот случай наступит, когда min->right == min и его нужно обработать отдельно. В случае, когда удаляемый элемент не является последним, то нужно выполнить процесс уплотнения кучи(consolidate):
int extract_min() {
node* res = min;
if (res) {
childs_in_root(res);
remove_root(res);
if (res->right == res)
min = 0;
else {
min = min->right;
consolidate();
}
}
int ans = res ? res->key : ERROR;
delete res;
return ans;
}
* This source code was highlighted with Source Code Highlighter.
4.3. Процесс уплотнения кучи(consolidate) лучше понять на иллюстрации кучи, которую мы получили на этапе процесса добавления новых элементов. На каждом шаге будут формироваться новые фибоначчиевы деревья размером равным степени двойки. Если на каком-то этапе получается два дерева одинакового размера они объединяются в одно и так повторяется до тех пор пока в наборе остаются деревья одинакового размера.
В итоге получаются 3 дерева уникального размера. Все корни циклического списка, который был вначале обработаны. На этом шаге процесс уплотнения кучи закончен. Отметим, что на текущем шаге уже известен минимальный корень кучи. Он определяется каждый раз, когда образуется дерево уникального размера.
После удаления минимального элемента “1” текущим элементом становится правый его брат “6”, образую первое фибоначчиево дерево размером 1.
Переходим к правому брату элемента “6”, т.к. к “7”, который образует дерево размером 1. Но на предыдущем шаге уже было получено дерево с таким размером. Объединяем их
При слиянии двух деревьев “6” и “7” минимальный корень двух деревьев становится общим корнем. А корень второго дерева становится сыном общего корня. После чего образуется новое дерево размером 2 – “6-7”. Увеличиваем счетчик детей у элемента “2”.
Следующим элементом становится “4”, образуя дерево размером 1. На текущем шаге имеется одно дерево размером 2 и одно дерево размером 1. Поэтому сливать деревья не надо
Новое дерево “2” имеет тот же размер, что и дерево “4”. Сливаем их.
После слияния получается дерево “2-4” размером 2. Но у нас уже есть дерево размером 2 – “6-7”. Поэтому сливаем сливаем эти деревья
При слиянии деревьев на предыдущем шаге образуется дерево размером 4, корнем которого является элемент “2”. Элемент “6” становится сыном элемента “2”. На рисунке нет явной связи “2” и “6”, потому что “6” включена в циклический список с “4”, который является сыном “2”.
Новый дерево “3” имеет уникальную размерность
Далее рассуждения можно продолжить по аналогии с предыдущими шагами.
Давайте теперь более детально разберем, что происходит в п. 4.1 и 4.2. Допустим, что на текущий момент уже удален минимальный элемент “1” и мы имеем:
Минимальным элементом кучи является 2.
В п.4.1. сказано, что нужно детей минимального элемента поместить в корневой список кучи, что мы и делаем. Далее элемент “2” удаляется и происходит сжатие кучи по вышеописанной схеме.
5. Изменение приоритета элемента
Осталась последняя операция, которую мы разберем. Очевидно, если новый приоритет элемента не ниже, чем приоритет его отца, то ничего делать не нужно. В противном случае действует по следующей схеме:
5.1. Удаляем текущий элемент A из кольцевого списка братьев и если отец A(P) ссылался на этот элемент A, то перебрасываем ссылку child элемента P на правого брата A. Уменьшаем счетчик количества сыновей у P и делаем метку mark равную true. Это означет, что у элемента P был удален сын. Данная метка указывает на то, что если возникнет такая ситуация, что у одного узла будет удалено более одного сына, то его нужно поместить в кольцевой список корней.
5.2 Добавляем элемент A в кольцевой список корней. Если приоритет элемента A меньше минимального корня, то элемент A становится минимальным элементом кучи.
5.3. Делаем каскадное вырезание. То, о чем идет речь в п.5.1. Если у отца элемента A – элемента P ранее удалялся сын, то необходимо выполнить поместить элемент P в кольцевой список корней. Далее продолжить п.5.3. для отца элемента P, если у него также ранее удалялись сыновья.
Задача: EZDIJKST
Решение: здесь
Примечание: полная реализация фибоначчиевой кучи
Автор: Беляев Игорь на 21:22 0 коммент. Ссылки на это сообщение
понедельник, 31 октября 2011 г.
Занятие №9 (Методы тестирования задач)
[Все занятия]
Практика: [Официальная страница]
Учебные задачи:
Задача A.
[Тестирование целых точек отрезка]
В тесте нет ничего сверхъестественного. Особое внимание нужно уделить случаю, когда точки лежат на прямой, параллельной одной из осей.
Задача B.
[Тестирование сортировки] [Генератор тестов]
С этой задачей я промучился очень долго. Я даже готовил слезный пост, с мольбами о помощи, в котором описал свои рассуждения по поводу этой задачи. Но так получилось, что когда был готов генератор тестов, первый же им сгенерированный набор зашел на OK. Приведу основной фрагмент того слезного поста:
” Какие тесты будем делать?
1) Генерируем рандомные числа во всем диапазоне. Размер массива немаксимален.
2) Все тоже самое, но размер массива максимален.
3) Упорядоченный массив. Лучше захватить и отрицательные и положительные числа
4) Обратный массив по аналогии с 3 тестом.
5) Массив из одного элемента(пускай отрицательного). Проверка на потенциальные Run-time errors.
6) Массив из двух элементов (отрицательного и положительного)
7) Массив не максимальной длины, который представляет собой кучу.
8) Массив с одинаковыми элементами. В том числе и по модулю. Так чтобы положительные числа были перед отрицательными.
9) Массив с одинаковыми элементами. Неотрицательными
10) Массив с одинаковыми элементами. Неположительными”.
Олимпиадные задачи:
Задача A.
[Распаковка строчки]
Задача для начинающих на аккуратную реализацию.
Задача B.
[Сортировка масс]
Нужно быть внимательным в выборе типов данных.
Задача C.
[Результаты олимпиады]
Несложная задача, но условие наводит ужас обилием различных вариантов проверок. На практике все оказалось не так страшно: само решение занимает меньше места чем ввод данных =)
Дополнительные олимпиадные задачи:
Задача A.
[Проверьте правильность ситуации]
С первого взгляда задача кажется несложной. Но нужно быть внимательным и аккуратным.
Задача B.
[Гражданская оборона]
Задача на умение писать компараторы. Удобно использовать граничные элементы, чтобы избежать лишние проверки.
Задача C.
[Переключение между окнами]
Задача на умение пользоваться списком и выполнять операции удаления элемента и вставки его в конец. Пришлось повозиться со случаем, когда имя программы представляет пробельные символы.
Автор: Беляев Игорь на 21:12 0 коммент. Ссылки на это сообщение
Алгоритм Кнута-Морриса-Пратта
По мотивам лекции Сагунова Данила и реализации indy256
Алгоритм относится к разряду алгоритмов поиска подстроки в строке.
Префиксом строки S называется подстрока строки S, первый символ которой совпадает с первым символом строки S.
Суффиксом строки S называется подстрока строки S, последний символ которой совпадает с последним символом строки S.
Длина префикса и суффикса строки S строго меньше длины строки S.
Префикс функция от строки S: П(S) – это максимальная длина префикса S, совпадающего с её суффиксом.
Z-функция от строки S – это массив длинной равной длине строки S, где Z[i] – это префикс функция от подстроки S, последний символ, которой равен S[i].
Пусть S = “abababaaabababac”
z[0] = П(“a”) = 0
z[1] = П(“ab”) = 0
z[2] = П(“aba”) = 1
z[3] = П(“abab”) = 2
z[4] = П(“ababa”) = 3
z[5] = П(“ababab”) = 4
z[6] = П(“abababa”) = 5
z[7] = П(“abababaa”) = 1
z[8] = П(“abababaaa”) = 1
z[9] = П(“abababaaab”) = 2
z[10] = П(“abababaaaba”) = 3
z[11] = П(“abababaaabab”) = 4
z[12] = П(“abababaaababa”) = 5
z[13] = П(“abababaaababab”) = 6
z[14] = П(“abababaaabababa”) = 7
z[15] = П(“abababaaabababac”) = 0
Можно заметить, что z-функция может увеличиваться за один шаг не более чем на 1, а уменьшиться на произвольное количество.
void prefix_func(const string &str, vector
z.resize(str.size());
z[0] = 0;
for (int i=1;i
while (pos > 0 && str[pos] != str[i])
pos = z[pos-1];
z[i] = pos + (str[pos] == str[i] ? 1 : 0);
}
}
* This source code was highlighted with Source Code Highlighter.
Ключевым моментов в функции подсчета Z-функции является цикл while(7-8 строки). На каждом шаге пытаемся увеличить длину префикса, равного суффиксу. Если это сделать не удается, то необходимо уменьшить размер префикса максимальным образом.
Рассмотрим нахождение z[7]. Текущая подстрока “abababaa”, z[6] = 5.
На шаге 7 пытаемся продолжить увеличивать длину префикса.
1) Сравниваем 5-ый символ с последним: ”abababaa”
2) Необходимо максимальным образом уменьшить длину префикса. Для этого нужно найти префикс префикса, который обязательно будет равен суффиксу суффикса. П(”ababa”) = 3
3) Сравниваем 3-ый символ с последним: “abababaa”. Продолжаем рассуждения пока префикс существует, т.е. пока имеет ненулевую длину, либо до совпадения концов префикса и суффикса. П(“aba”) = 1.
4) Сравниваем 1-ый символ с последним: “abababaa”. П(“a”) = 0.
5) Сравниваем 0-ой символ с последним: “abababaa”. Успех =)
Значит z[7] = 1.
Вернемся к исходной задаче поиска подстроки(S) в строке(TEXT). Если не хочется заморачиваться, а главное если есть такая возможность, то в общем случае можно получить строку TEXT’ = S + sep + TEXT, где sep – это символ, который гарантированно не встречается в строках S и TEXT, а “+” – это конкатенация строк. Затем найти z-функцию от TEXT’. Если z[i] = длина(S), значит S является подстрокой строки TEXT.
void kmp() {
text = str + "#" + text;
z.resize(text.size(), -1);
z[0] = 0;
for (int i=1;i
while (pos != -1 && text[i] != text[pos])
pos = pos - 1 >= 0 ? z[pos-1] : -1;
z[i] = pos + 1;
}
}
void output() {
for (int i=0;i
cout<< i - 2*str.size() <<' ';
}
}
}
* This source code was highlighted with Source Code Highlighter.
Понятно, что в данной реализации происходит лишнее выделение памяти, и не всегда есть возможность вести себя так вальяжно.
Более эффективная реализация:
void prefix_func(const string &str, vector
z.resize(str.size());
z[0] = 0;
for (int i=1;i
while (pos > 0 && str[pos] != str[i])
pos = z[pos-1];
z[i] = pos + (str[pos] == str[i] ? 1 : 0);
}
}
void kmp(const string &text, const string &str) {
vector
prefix_func(str,z);
int pos = 0;
for (int i=0; i
pos = z[pos-1];
if (text[i] == str[pos]) pos++;
if (pos == str.size())
printf("%d ", i - pos + 1);
}
}
* This source code was highlighted with Source Code Highlighter.
Здесь сначала считается z-функция для строки S, а потом происходит эмуляция первой реализации, как будто строка S является префиксом строки TEXT. Как видно в данном случае затраты на память сократятся.
Попрактиковаться можно здесь:
spoj.pl - NHAY
acmp.ru – Поиск подстроки
Автор: Беляев Игорь на 8:58 1 коммент. Ссылки на это сообщение
воскресенье, 23 октября 2011 г.
Занятие №8. Динамическое программирование с двумя и более параметрами
Теория: Лекция [Все занятия]
Практика: [Официальная страница]
Учебные задачи:
Задача A.
[Наибольшая общая подпоследовательность (НОП)]
В данной задаче можно применить классический алгоритм Нудельмана-Вунша.
Задача B.
[Наибольшая общая подпоследовательность с восстановлением ответа]
Продолжение предыдущей задачи с той разницей, что в текущей реализации использовались барьерные первый столбец и строка.
Задача C.
[Биномиальные коэффициенты]
Наверное последняя проходная задача на ДП в этом цикле. Суть задачи сводиться к классической черепашке.
Олимпиадные задачи:
Задача A.
[Движение по полосам]
Очень хорошая задача. Решаем ДП с двумя параметрами: количество использованных полос(s), количество использованных дорог(r). Ответом на вопрос будет являться значение dp(n,m), где n – общее количество полос, m – общее количество дорог. Чтобы найти значение на текущем шаге dp(s,r), необходимо перебрать и сложить все возможные значения dp(s-1,r’).
Задача B.
[Еловая аллея]
Данная реализация отражает идею, предложенную в разборе, но имеет сложность M*M*N.
Задача C.
[Почти палиндром]
Классическая LR динамика. Нужно быть осторожным в выборе типа данных для элементов таблицы.
Дополнительные олимпиадные задачи:
Задача A.
[Электронная почта]
Суть задачи сводится к поиску оптимальной стратегии в игре Zuma, с одним только отличием, что нет минимального количества рядом стоящих шариков, которые могут быть удалены за один раз. В обычной игре это число равно 3. На spoj.pl есть задача ZUMA, в которой как раз фигурирует это минимальное значение рядом стоящих шариков.
Решать будем двумерной LR динамикой. В таблице dp[i][j] находится оптимальный ответ для подмассива с i-ого по j-ый элементы. Базой динамики будут служить два факта:
1) if (i > j) dp[i][j] = 0
2) if (i == j) dp[i][j] = 1
Теперь рассмотрим общий случай для произвольных i и j:
I) Очевидно, что может быть такая ситуация, когда исходный массив можно разбить на набор непересекающихся подмассивов и последовательно избавиться от каждого из них. Например для массива A = {1, 2, 2, 3, 4, 5, 5, 5} это будет оптимальная стратегия. Этот случай обрабатывается в строках 40-41.
II) Отдельно стоит рассмотреть случай, когда элементы a[i] и a[j] равны. Возможно стоит сначала избавиться от подмассива [i+1, j-1], а потом за одну итерацию убрать крайние элементы за одну итерацию. Например для массива B = {1,,2,3,4,5,5,5,4,3,2,1} это будет оптимальная стратегия. Этот случай обрабатывается в строке 44.
III) Продолжим рассматривать случай, когда граничные элементы подмассива равны. Может возникнуть такая ситуация, когда есть элемент a[i] == a[k] == a[j], причем i < k < j. При этом выгодно сначала избавиться от подмассива [i+1,k-1], чтобы элементы a[i] и a[k] встали рядышком, либо же избавиться от подмассива [k+1,j-1], чтобы рядом оказались элементы a[k] и a[j]. Например для массива С = {1,2,3,4,3,2,1,5,6,7,6,5,1} оптимальной стратегия будет III с элементами II(для удаления подмассивов межды единицами). Этот момент обрабатывается в строках 45-49.
Задача B.
[Плитки]
Шикарная задача на динамику по рванному краю(динамика по профилю).
Будем заполнять таблицу dp[clr][len][mask], где clr – цвет, на который заканчивается последовательность длины len, удовлетворяющая битовой маске mask. Разберемся с битовой маской.
Сразу оговоримся, что предложенное решение использует маску, ориентированную на несимметричную матрицу цветов. Условно обозначим 3 возможных цвета как R,G и B. Тогда имеем матрицу:
R G B
R 0 1 2
G 3 4 5
B 6 7 8
На пересечении цветов указано значение row * 3 + col, где row – номер строки, col – номер столбца. Получаем следующий массив:
8 7 6 5 4 3 2 1 0 - номер сочетания цветов
BB BG BR GB GG GR RB RG RR - сочетание цветов
Пусть номер сочетания цветов указывает на бит в маске.
Зафиксируем для таблицы dp значение clr, len и mask. Номер единичного бита в mask говорит о том, что сочетание цветов, соответствующего номеру бита уже было в конце строки в диапазоне [len,n-1].
Отсюда можно получить базу динамики. Перебрав все пары цветов c1 и с2, в случае валидной комбинации c1-c2 dp[c1][n-2][code(c1,c2)] = 1. Случай, когда длина строки равна 1 можно рассмотреть отдельно.
Подсчет всех остальных значений отображен в строках 104-120:
Для фиксированных c1, c2, len, mask можно однозначно определить ответ:
dp[c1][len][mask] = dp[c2][len+1][mask] + dp[c2][len+1][mask ^ cur_mask], где cur_mask – закодированная комбинация цветов c1 и с2. Говоря другими словами последовательность, заканчивающаяся цветом c1 длины len и маской mask могла получиться из строки, заканчивающейся цветом c2, длины len+1 с той же маской, а также маской, в которой ранее не использовалось сочетание цветов c1 и с2.
Ответ формируется из элементов dp[c][0][mask], где с принимает все возможные значения цветов, а mask принимает все возможные валидные комбинации цветов, содержащие всю матрицу цветов.
Задача C.
[Симпатичные узоры возвращаются]
Задача является логическим продолжением задачи Симпатичные узоры, которое наверное является классикой динамики по рваному контуру. Ее разбор дан в лекции. Здесь лежит мое решение.
Исходная задача также разобрана в лекции. Суть ее сводится к быстрому перемножению матриц. Данный подход использовался в алгоритме для нахождения достижимости за k шагов произвольной вершины j из произвольной вершины i. Там нужно было возвести исходную матрицу смежности в степень k.
Автор: Беляев Игорь на 17:54 0 коммент. Ссылки на это сообщение
четверг, 20 октября 2011 г.
Система непересекающихся множеств (Disjoint set union)
Если мы работаем с объектами, которые во время работы могут объединяться в группы. Причем эти группы попарно не имеют общих элемент(непересекающиеся множества). То скорее всего нам пригодится структура данных “Система непересекающихся множеств” (DSU). С помощью нее можно сделать две операции:
1) int find_set(X) - определение множества, в котором находится элемент X. При этом множество определяется одним(лидирующим) элементом.
2) void union_set(X,Y) - объединение множества, в котором находится элемент X с множеством, в котором находится элемент Y.
Полный обзор этой темы можно найти на емаксе.
Множества будут представлены в виде леса(набор деревьев), т.е. каждое множество будет являться деревом. При этом для каждого элемента будет храниться его предок. Это проще всего сделать с помощью массива parent. В начальный момент времени каждый элемент будет являться предком для самого себя, т.е. каждое дерево состоит из одного элемента.
void init() {
for (int i=1;i<=n;i++)
parent[i] = i;
}
* This source code was highlighted with Source Code Highlighter.
Теперь давайте подумаем как можно реализовать функцию find_set. В качестве лидирующего элемента нужно брать корневой элемент дерева, т.к. только он является общим для всех элементов дерева. В самой простой реализации можно последовательно добраться из текущей вершины до корневой за линейное время. Отметим тот факт, что с большой вероятностью придется проделывать этот путь много раз, поэтому сразу появляется первая эвристика. Можно один раз определить корневой узел для текущей вершины и назначить его родителем. Тоже самое нужно проделать для каждой вершины, которая встречается на пути от текущей вершины до корневой.
int find_set(int x) {
if (parent[x] == x)
return x;
return parent[x] = find_set(parent[x]);
}
* This source code was highlighted with Source Code Highlighter.
Теперь давайте рассмотрим операцию объединения двух множеств. При объединении двух множеств выбирается один лидирующий элемент. Очевидно, что он должен быть лидирующим элементов одного из объединяемых множеств. Какое же множество выбрать? Нужно меньшее множество присоединять к большему. Это целесообразно, потому что придется переопределять нового предка для меньшего количества элементов.
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if(x != y) {
if (size[x] < size[y])
swap(x,y);
parent[y] = x;
size[x] += size[y];
}
}
* This source code was highlighted with Source Code Highlighter.
Как видно был заведен еще один массив size, в котором на [i] месте хранится количество элементов в дереве, корнем которого является элемент [i]. Но можно обойтись без дополнительного массива подружившись с рандомом.
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if (rand()&1)
parent[x] = y;
else
parent[y] = x;
}
* This source code was highlighted with Source Code Highlighter.
Как показывает практика существенных замедлений такое решение не дает.
Существенным минусом DSU является то, что нельзя одно множество разбить на два. Но даже несмотря на это у DSU целый паровоз применений (см. емакс)
Для закрепления материала предлагаю решить две несложные задачи:
1) [Острова] (DSU в чистом виде) [Решение]
2) [Паутина Ананси] [Решение]
कोई टिप्पणी नहीं:
एक टिप्पणी भेजें