🌲 10.3: Quick-Union Algoritması

class QuickUnion:
    """
    Quick-Union Implementasyonu
    
    Lazy Approach (Tembel Yaklaşım):
    - Elemanları ağaç yapısında tut
    - Union: Sadece bir pointer değiştir
    - Find: Köke kadar yürü
    
    Veri yapısı:
    - parent[i]: i'nin ebeveyni
    - parent[i] == i ise, i bir root
    """
    
    def __init__(self, n: int):
        """
        N nesne ile Union-Find oluştur.
        Başlangıçta her eleman kendi ağacı (N root).
        """
        self.parent = list(range(n))  # Herkes kendi parent'ı
        self.n = n
        self._count = n
    
    def find(self, p: int) -> int:
        """
        p'nin root'unu bul.
        
        Root'a ulaşana kadar parent'ları takip et.
        Root: parent[x] == x olan eleman.
        
        Zaman: O(ağaç yüksekliği) - en kötü O(N)
        """
        while self.parent[p] != p:
            p = self.parent[p]
        return p
    
    def connected(self, p: int, q: int) -> bool:
        """p ve q aynı ağaçta mı?"""
        return self.find(p) == self.find(q)
    
    def union(self, p: int, q: int) -> None:
        """
        p ve q'nun ağaçlarını birleştir.
        
        Algoritma:
        1. Her ikisinin root'unu bul
        2. p'nin root'unu q'nun root'una bağla
        
        Zaman: O(ağaç yüksekliği) - find maliyeti
        """
        root_p = self.find(p)
        root_q = self.find(q)
        
        if root_p == root_q:
            return  # Zaten aynı ağaçta
        
        # p'nin root'unu q'nun root'una bağla
        self.parent[root_p] = root_q
        self._count -= 1
    
    def count(self) -> int:
        return self._count
    
    def display_tree(self, root=None):
        """Ağaç yapısını göster"""
        if root is None:
            # Tüm root'ları bul
            roots = [i for i in range(self.n) if self.parent[i] == i]
            print(f"Orman ({len(roots)} ağaç):")
            for r in roots:
                self.display_tree(r)
            return
        
        # Belirli bir root'un ağacını göster
        children = [i for i in range(self.n) if self.parent[i] == root and i != root]
        
        def get_descendants(node):
            result = [node]
            for i in range(self.n):
                if self.parent[i] == node and i != node:
                    result.extend(get_descendants(i))
            return result
        
        members = get_descendants(root)
        print(f"  Root {root}: {sorted(members)}")


# ===== DEMO =====
print("=" * 60)
print("QUICK-UNION DEMO")
print("=" * 60)

qu = QuickUnion(10)
print(f"\nBaşlangıç:")
print(f"parent[]: {qu.parent}")
qu.display_tree()

operations = [
    ("union", 4, 3),
    ("union", 3, 8),
    ("union", 6, 5),
    ("union", 9, 4),
    ("union", 2, 1),
    ("query", 8, 9),
    ("query", 5, 4),
    ("union", 5, 0),
    ("union", 7, 2),
    ("union", 6, 1),
    ("query", 0, 7),
]

print("\n" + "─" * 60)

for op in operations:
    if op[0] == "union":
        _, p, q = op
        print(f"\nunion({p}, {q}):")
        qu.union(p, q)
        print(f"parent[]: {qu.parent}")
        qu.display_tree()
    else:
        _, p, q = op
        # Root'ları göster
        root_p, root_q = qu.find(p), qu.find(q)
        result = root_p == root_q
        symbol = "✓" if result else "✗"
        print(f"\nconnected({p}, {q})?")
        print(f"  root({p})={root_p}, root({q})={root_q}")
        print(f"  Sonuç: {result} {symbol}")

class QuickUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.n = n
        self.find_steps = 0  # Adım sayacı
    
    def find(self, p):
        steps = 0
        while self.parent[p] != p:
            p = self.parent[p]
            steps += 1
        self.find_steps += steps
        return p
    
    def union(self, p, q):
        root_p = self.find(p)
        root_q = self.find(q)
        if root_p != root_q:
            self.parent[root_p] = root_q


# En kötü durum: Uzun zincir oluştur
print("=" * 50)
print("QUICK-UNION: EN KÖTÜ DURUM")
print("=" * 50)

n = 10
qu = QuickUnion(n)

print(f"\n{n} elemanlı yapı")
print("\nUnion işlemleri (kötü sıra):")

# Kötü sırayla union
for i in range(n - 1):
    qu.union(i, i + 1)
    print(f"  union({i}, {i+1})")

print(f"\nparent[]: {qu.parent}")

# Ağaç yapısını göster
print("\nOluşan ağaç (zincir):")
print(f"  {n-1}")
for i in range(n-2, -1, -1):
    print(f"  |")
    print(f"  {i}")

# Find maliyeti
print(f"\nFind maliyeti testi:")
qu.find_steps = 0

for i in range(n):
    steps_before = qu.find_steps
    root = qu.find(i)
    steps_taken = qu.find_steps - steps_before
    print(f"  find({i}) → {root} ({steps_taken} adım)")

print(f"\nToplam adım: {qu.find_steps}")
print(f"Ortalama: {qu.find_steps / n:.1f} adım/find")
print(f"\n⚠️ find(0) için {n-1} adım gerekti! (O(N))")