⚡ 10.2: Quick-Find Algoritması

class QuickFind:
    """
    Quick-Find Union-Find Implementasyonu
    
    Eager Approach (İstekli Yaklaşım):
    - Find çok hızlı: O(1)
    - Union yavaş: O(N)
    
    Veri yapısı:
    - id[i]: i elemanının küme ID'si
    - Aynı kümedeki tüm elemanlar aynı ID'ye sahip
    """
    
    def __init__(self, n: int):
        """
        N nesne ile Union-Find oluştur.
        Başlangıçta her nesne kendi kümesinde.
        
        Zaman: O(N)
        Alan: O(N)
        """
        # Her eleman kendi ID'sine sahip
        self.id = list(range(n))
        self.n = n
        self._count = n  # Küme sayısı
    
    def find(self, p: int) -> int:
        """
        p'nin küme ID'sini döndür.
        
        Zaman: O(1) - sadece dizi erişimi
        """
        return self.id[p]
    
    def connected(self, p: int, q: int) -> bool:
        """
        p ve q aynı kümede mi?
        
        Zaman: O(1)
        """
        return self.find(p) == self.find(q)
    
    def union(self, p: int, q: int) -> None:
        """
        p ve q'nun kümelerini birleştir.
        
        Zaman: O(N) - tüm diziyi taramak gerekiyor!
        
        Algoritma:
        1. p ve q'nun ID'lerini bul
        2. Eğer aynıysa: birşey yapma
        3. Değilse: p'nin ID'sine sahip TÜM elemanları
           q'nun ID'sine değiştir
        """
        pid = self.find(p)
        qid = self.find(q)
        
        # Zaten aynı kümedeler
        if pid == qid:
            return
        
        # p'nin ID'sine sahip tüm elemanları değiştir
        # Bu O(N) işlem!
        for i in range(self.n):
            if self.id[i] == pid:
                self.id[i] = qid
        
        self._count -= 1  # Bir küme azaldı
    
    def count(self) -> int:
        """Kaç ayrı küme var?"""
        return self._count
    
    def display(self):
        """Mevcut durumu göster"""
        print(f"id[]: {self.id}")
        
        # Kümeleri grupla
        groups = {}
        for i in range(self.n):
            gid = self.id[i]
            if gid not in groups:
                groups[gid] = []
            groups[gid].append(i)
        
        print(f"Kümeler ({self.count()} adet):")
        for gid, members in sorted(groups.items()):
            print(f"  ID={gid}: {members}")


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

qf = QuickFind(10)
print(f"\nBaşlangıç ({qf.n} eleman, {qf.count()} küme):")
qf.display()

# İşlemler
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)
print("İşlemler:")
print("─" * 60)

for op in operations:
    if op[0] == "union":
        _, p, q = op
        print(f"\nunion({p}, {q}):")
        qf.union(p, q)
        qf.display()
    else:
        _, p, q = op
        result = qf.connected(p, q)
        symbol = "✓" if result else "✗"
        print(f"\nconnected({p}, {q})? → {result} {symbol}")

import time

class QuickFind:
    def __init__(self, n):
        self.id = list(range(n))
        self.n = n
        self.array_accesses = 0  # Dizi erişim sayacı
    
    def find(self, p):
        self.array_accesses += 1
        return self.id[p]
    
    def union(self, p, q):
        # 2 find işlemi
        pid = self.find(p)
        qid = self.find(q)
        
        if pid == qid:
            return
        
        # N elemana bak, eşleşenleri değiştir
        for i in range(self.n):
            self.array_accesses += 1  # Okuma
            if self.id[i] == pid:
                self.id[i] = qid
                self.array_accesses += 1  # Yazma


def test_quick_find(n, m):
    """N elemanlı yapıda M rastgele union yap"""
    import random
    random.seed(42)
    
    qf = QuickFind(n)
    start = time.time()
    
    for _ in range(m):
        p = random.randint(0, n-1)
        q = random.randint(0, n-1)
        qf.union(p, q)
    
    elapsed = time.time() - start
    return elapsed, qf.array_accesses


print("=" * 60)
print("QUICK-FIND MALİYET ANALİZİ")
print("=" * 60)
print(f"\n{'N':>10} {'M işlem':>12} {'Süre (s)':>12} {'Dizi Erişimi':>15}")
print("-" * 60)

# Farklı boyutlarda test
test_cases = [
    (100, 100),
    (1000, 1000),
    (5000, 5000),
    (10000, 10000),
]

for n, m in test_cases:
    elapsed, accesses = test_quick_find(n, m)
    print(f"{n:>10,} {m:>12,} {elapsed:>12.4f} {accesses:>15,}")

print("\n" + "─" * 60)
print("💡 Gözlem:")
print("─" * 60)
print("""
Her union işlemi O(N) maliyet!
N büyüdükçe dizi erişimi N² gibi artıyor.

Bu çok pahalı:
- N = 10⁹ (1 milyar) nesne
- N union işlemi
- Toplam: 10⁹ × 10⁹ = 10¹⁸ dizi erişimi!
- Saniyede 10⁹ işlem yapan bilgisayarda: 30+ yıl!
""")