union-find

DSU (birlashtiriladigan to‘plamlar) — «a va b bir guruhdami?» va «guruhlarni birlashtir» so‘rovlariga deyarli O(1) da javob beradi.

parent = list(range(n))
size = [1] * n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # yo‘lni qisqartirish
        x = parent[x]
    return x

def union(a, b):
    a, b = find(a), find(b)
    if a == b:
        return False
    if size[a] < size[b]:
        a, b = b, a
    parent[b] = a
    size[a] += size[b]
    return True

Qo‘llanishi

• Kruskal — minimal skelet daraxt: qirralarni vazn bo‘yicha saralab, sikl hosil qilmaganlarini olish.
• Dinamik bog‘lanish: «qirralar qo‘shilib boradi, nechta komponenta qoldi?»
• Ekvivalent elementlarni guruhlash (bir xil email’li akkauntlar va h.k.).