Система непересекающихся множеств (Disjoint set union)

Если мы работаем с объектами, которые во время работы могут объединяться в группы. Причем эти группы попарно не имеют общих элемент(непересекающиеся множества). То скорее всего нам пригодится структура данных “Система непересекающихся множеств” (DSU). С помощью нее можно сделать две операции:
1) int find_set(X) - определение множества, в котором находится элемент X. При этом множество определяется одним(лидирующим) элементом.
2) void union_set(X,Y) - объединение множества, в котором находится элемент X с множеством, в котором находится элемент Y.

Полный обзор этой темы можно найти на емаксе.

Множества будут представлены в виде леса(набор деревьев), т.е. каждое множество будет являться деревом. При этом для каждого элемента будет храниться его предок. Это проще всего сделать с помощью массива parent. В начальный момент времени каждый элемент будет являться предком для самого себя, т.е. каждое дерево состоит из одного элемента.

1. void init() {
2.   for (int i=1;i<=n;i++)
3.     parent[i] = i;
4. }

* This source code was highlighted with Source Code Highlighter.

Теперь давайте подумаем как можно реализовать функцию find_set. В качестве лидирующего элемента нужно брать корневой элемент дерева, т.к. только он является общим для всех элементов дерева. В самой простой реализации можно последовательно добраться из текущей вершины до корневой за линейное время. Отметим тот факт, что с большой вероятностью придется проделывать этот путь много раз, поэтому сразу появляется первая эвристика. Можно один раз определить корневой узел для текущей вершины и назначить его родителем. Тоже самое нужно проделать для каждой вершины, которая встречается на пути от текущей вершины до корневой.

1. int find_set(int x) {
2.   if (parent[x] == x)
3.     return x;
4.   return parent[x] = find_set(parent[x]);
5. }

* This source code was highlighted with Source Code Highlighter.

Теперь давайте рассмотрим операцию объединения двух множеств. При объединении двух множеств выбирается один лидирующий элемент. Очевидно, что он должен быть лидирующим элементов одного из объединяемых множеств. Какое же множество выбрать? Нужно меньшее множество присоединять к большему. Это целесообразно, потому что придется переопределять нового предка для меньшего количества элементов.

1. void union_set(int x, int y) {
2.   x = find_set(x);
3.   y = find_set(y);
4.   if(x != y) {
5.     if (size[x] < size[y])
6.       swap(x,y);
7.     parent[y] = x;
8.     size[x] += size[y];
9.   }
10. }

* This source code was highlighted with Source Code Highlighter.

Как видно был заведен еще один массив size, в котором на [i] месте хранится количество элементов в дереве, корнем которого является элемент [i]. Но можно обойтись без дополнительного массива подружившись с рандомом.

1. void union_set(int x, int y) {
2.   x = find_set(x);
3.   y = find_set(y);
4.   if (rand()&1)
5.     parent[x] = y;
6.   else
7.     parent[y] = x;
8. }

* This source code was highlighted with Source Code Highlighter.

Как показывает практика существенных замедлений такое решение не дает.
Существенным минусом DSU является то, что нельзя одно множество разбить на два. Но даже несмотря на это у DSU целый паровоз применений (см. емакс)

Для закрепления материала предлагаю решить две несложные задачи:
1) [Острова] (DSU в чистом виде) [Решение]
2) [Паутина Ананси] [Решение]