Qrafa qövslər əlavə olunur və hər an soruşulur: a və b eyni komponentdədirmi? Hər dəfə BFS/DFS işlətmək O(V + E) edir. Union-Find (Disjoint Set Union, DSU) komponentləri çoxluqlar kimi saxlayır və bu sualı demək olar ki, O(1)-də cavablandırır.

Solda yolun sıxılması, sağda ölçüyə görə birləşdirmə
Solda yolun sıxılması, sağda ölçüyə görə birləşdirmə

İdeya: meşə

Hər çoxluq bir ağacdır, ağacın kökü çoxluğun nümayəndəsidir. Meşə bir massivdədir: parent[i] — i-nin valideyni, parent[r] == r olarsa r kökdür. find(x) kökə qədər gedir, union(a, b) bir kökü digərinin altına asır.

Əgər həmişə eyni tərəfi asırıqsa, ağac zəncirə çevrilir və find O(n) olur. Aşağıda 1000 ardıcıl birləşdirmədə fərq görünür.

python
def depth(parent, x):
    d = 0
    while parent[x] != x:
        x, d = parent[x], d + 1
    return d

def find(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x

n = 1000
naive = list(range(n))
by_size, size = list(range(n)), [1] * n
for i in range(n - 1):
    naive[find(naive, i)] = find(naive, i + 1)          # always hang the left root
    a, b = find(by_size, i), find(by_size, i + 1)
    if size[a] < size[b]:
        a, b = b, a
    by_size[b] = a                                     # small tree under the large
    size[a] += size[b]