Union-Find (Disjoint Set Union) veri yapısını path compression ve union by rank ile yazın. Hangi problemlerde kullanılır?

Union-Find, elemanları ayrık kümelere bölen ve iki işlemi neredeyse sabit zamanda yapan bir yapıdır: find(x) (x'in kümesinin temsilcisi) ve union(a, b) (iki kümeyi birleştir). İki optimizasyonla amortize maliyet O(α(n)) olur; α ters Ackermann fonksiyonudur ve pratikte en fazla 4'tür.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # zaten aynı kümede -> döngü
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra             # union by rank
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True

Optimizasyonlar

• Path compression: find sırasında yol üzerindeki her düğümü doğrudan köke bağlar; sonraki aramalar kısalır.
• Union by rank/size: küçük ağacı büyük ağacın altına bağlar; ağaç yüksekliği O(log n) ile sınırlı kalır.

Kullanım alanları

• Yönsüz grafta döngü tespiti (union False dönerse döngü vardır).
• Kruskal minimum spanning tree algoritması.
• Bağlı bileşen sayısı (Number of Provinces, Number of Islands II).
• Redundant Connection, Accounts Merge, sosyal ağda arkadaş grupları.

Örnek: Redundant Connection

def find_redundant(edges):
    dsu = DSU(len(edges) + 1)
    for a, b in edges:
        if not dsu.union(a, b):
            return [a, b]

print(find_redundant([[1, 2], [1, 3], [2, 3]]))  # [2, 3]

Union-Find yönlü graflarda döngü tespiti için uygun değildir; orada DFS veya topolojik sıralama kullanılır.