Как это хранить

Индексы массива - наш юниверс, т.е. элементы. Значения по этим индексам - номер disjoint set, к которому этот элемент принадлежит.

makeSet(x) - $O(1)$

void makeSet(x) {
	arr[x] = groupID; 
	groupID++; 
}

groupID - текущий свободный индекс в массиве.

find(x) - $O(1)$

int find(x) {
	return arr[x]; 
}

union(x, y) - $O(n)$

void union(x, y) {
	// всем элементам y ставим номера x
	for (int i = 0; i < n; i++) {
		if (arr[i] == arr[y]) {
			arr[i] = arr[x]; 
		}
	}
}