Это довольно поздний ответ, но, вероятно, на стеке не было ответа в других местах, и, поскольку это самая верхняя страница для тех, кто ищет union-find, вот подробное решение.
Find-Union - очень быстрая операция, выполняемая в почти постоянное время.
Это следует из представления Джереми о сжатии пути и отслеживании размеров набора. Сжатие пути выполняется для каждой операции поиска, тем самым занимая амортизированное время lg * (n). lg * подобен обратной функции Аккермана, которая растет настолько медленно, что редко превышает 5 (по крайней мере, до n <2 ^ 65535). Объединение / слияние наборов выполняется лениво, просто указывая один корень на другой, в частности корень меньшего набора на корень большего набора, что завершается за постоянное время. </p>
См. Код ниже https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp
class UF {
int *id, cnt, *sz;
public:
// Create an empty union find data structure with N isolated sets.
UF(int N) {
cnt = N; id = new int[N]; sz = new int[N];
for (int i = 0; i<N; i++) id[i] = i, sz[i] = 1; }
~UF() { delete[] id; delete[] sz; }
// Return the id of component corresponding to object p.
int find(int p) {
int root = p;
while (root != id[root]) root = id[root];
while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
return root;
}
// Replace sets containing x and y with their union.
void merge(int x, int y) {
int i = find(x); int j = find(y); if (i == j) return;
// make smaller root point to larger one
if (sz[i] < sz[j]) { id[i] = j, sz[j] += sz[i]; }
else { id[j] = i, sz[i] += sz[j]; }
cnt--;
}
// Are objects x and y in the same set?
bool connected(int x, int y) { return find(x) == find(y); }
// Return the number of disjoint sets.
int count() { return cnt; }
};