Многие алгоритмы используют представление множеств в виде набора непересекающихся подмножеств, которые можно по-разному комбинировать. Для этой цели можно воспользоваться средствами работы с множествами, имеющимися в современных языках программирования, однако их реализации не гарантируют, что различные подмножества действительно будут непересекающимися. Кроме того, средства обработки множеств имеются не во всех языках программирования. В этом параграфе мы рассмотрим способ реализации разбиений множеств на массивах. Подобные алгоритмы могут принести пользу при реализации алгоритма Крускала построения минимального остовного поддерева.
     Начнем с массива Parent, в котором под каждый элемент множества, с которым мы собираемся работать, отведена одна ячейка. Вначале мы полагаем значения всех элементов равными -1. Знак - означает здесь, что каждый элемент является корнем разбиения, а абсолютное значение 1 - что соответствующая часть разбиения состоит из одного элемента. При работе алгоритма значения ячеек будут меняться, и, скажем, значение -7 указывает на то, что соответствующий элемент является корнем части, состоящей из семи элементов. При добавлении элемента к части значение соответствующей ему ячейки добавляется к значению корня. Если, к примеру, пятый элемент добавляется к части, корень которой - восьмой элемент массива Parent, то в пятую ячейку записывается значение 8, а отрицательное содержимое восьмой ячейки будет увеличено по абсолютной величине, чтобы указать на появление дополнительного элемента. При объединении двух частей разбиения происходит изменение только корневых ячеек этих частей, поэтому каждый элемент массива ссылается на своего непосредственного предка.


     Рассмотрим разбиение, изображенное на рис. 1. Видно, что оно состоит из трех частей с корнями 5, 6 и 11. В этих ячейках записаны отрицательные значения, модули которых равны числу элементов в соответствующем разбиении. Во всех остальных ячейках хранятся номера их непосредственных предков. Если мы захотим объединить части с корнями 6 и 11, то нужно в ячейку Parent[11] занести значение 6 - новый корень объединенной части, а в ячейку 6 - значение -5, модуль которого равен числу элементов в объединении двух частей. Вот алгоритмы, реализующие эту структуру разбиений:

InitializePartition(N)
N	число элементов в множестве
for i = 1 to N do
	Parent[i] = -1
end for
			

Union(i, j)
i, j	объединяемые части разбиения

totalElements = Parent[i] + Parent[j]
if Parent[i] >= Parent[i] + Parent[j] then
	Parent[i] = j
	Parent[j] = totalElements
else
	Parent[j] = i
	Parent[i] = totalElements
end if
			

FindRoot(s)
s	элемент, для которого мы хотим найти корень части, 
его содержащий

result = s
while Parent[result] > 0 do
	resut = Parent[result]
end while
return result