⚡ 10.5: Path Compression

class UnionFind:
    """
    Optimize Edilmiş Union-Find
    
    Weighted Quick-Union + Path Compression
    
    Her işlem: O(α(N)) amortize ≈ O(1) pratikte
    
    α(N) = Inverse Ackermann fonksiyonu
    - Evrendeki atom sayısı (10^80) için bile α(N) < 5
    - Pratikte sabit kabul edilebilir
    """
    
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n  # Union by rank
        self.n = n
        self._count = n
    
    def find(self, p: int) -> int:
        """
        Path Compression ile root bul.
        
        İki geçişli versiyon:
        1. Root'u bul
        2. Yoldaki tüm düğümleri root'a bağla
        
        Amortize O(α(N)) ≈ O(1)
        """
        # Root'u bul
        root = p
        while self.parent[root] != root:
            root = self.parent[root]
        
        # Path Compression: yoldaki herkesi root'a bağla
        while p != root:
            next_p = self.parent[p]
            self.parent[p] = root
            p = next_p
        
        return root
    
    def find_halving(self, p: int) -> int:
        """
        Alternatif: Path Halving (tek geçiş)
        
        Her düğümü dedesine bağla.
        Daha az işlem, pratikte aynı performans.
        """
        while self.parent[p] != p:
            self.parent[p] = self.parent[self.parent[p]]  # Dede'ye atla
            p = self.parent[p]
        return p
    
    def union(self, p: int, q: int) -> bool:
        """
        Union by Rank ile birleştir.
        
        Amortize O(α(N)) ≈ O(1)
        """
        root_p = self.find(p)
        root_q = self.find(q)
        
        if root_p == root_q:
            return False  # Zaten bağlı
        
        # Union by Rank
        if self.rank[root_p] < self.rank[root_q]:
            self.parent[root_p] = root_q
        elif self.rank[root_p] > self.rank[root_q]:
            self.parent[root_q] = root_p
        else:
            self.parent[root_q] = root_p
            self.rank[root_p] += 1
        
        self._count -= 1
        return True
    
    def connected(self, p: int, q: int) -> bool:
        return self.find(p) == self.find(q)
    
    def count(self) -> int:
        return self._count


# ===== DEMO =====
print("=" * 60)
print("WEIGHTED QUICK-UNION + PATH COMPRESSION")
print("=" * 60)

uf = UnionFind(10)

# Union işlemleri
unions = [(4,3), (3,8), (6,5), (9,4), (2,1), (5,0), (7,2), (6,1), (8,0)]
for p, q in unions:
    uf.union(p, q)

print("\nUnion işlemleri sonrası:")
print(f"parent[]: {uf.parent}")
print(f"rank[]:   {uf.rank}")
print(f"Küme sayısı: {uf.count()}")

# Path compression etkisini göster
print("\n" + "─" * 60)
print("Path Compression Etkisi:")
print("─" * 60)

# 9'dan root'a git - önce parent dizisine bak
print(f"\nfind(9) öncesi parent[]: {uf.parent}")

# find çağır
root = uf.find(9)
print(f"find(9) = {root}")

# Sonra parent dizisine bak
print(f"find(9) sonrası parent[]: {uf.parent}")
print("\n→ Path compression ağacı düzleştirdi!")

class UnionFindVerbose:
    """Path Compression'ı adım adım gösteren versiyon"""
    
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find_verbose(self, p):
        """Path compression'ı adım adım göster"""
        original_p = p
        path = [p]
        
        # 1. Root'a kadar git, yolu kaydet
        while self.parent[p] != p:
            p = self.parent[p]
            path.append(p)
        root = p
        
        print(f"  İzlenen yol: {' → '.join(map(str, path))}")
        print(f"  Root = {root}")
        
        # 2. Path compression
        if len(path) > 2:
            print(f"  Sıkıştırma:")
            for node in path[:-1]:  # Root hariç
                if self.parent[node] != root:
                    print(f"    parent[{node}] = {self.parent[node]} → {root}")
                    self.parent[node] = root
        
        return root
    
    def union(self, p, q):
        rp = self.find(p)
        rq = self.find(q)
        if rp != rq:
            if self.rank[rp] < self.rank[rq]:
                self.parent[rp] = rq
            elif self.rank[rp] > self.rank[rq]:
                self.parent[rq] = rp
            else:
                self.parent[rq] = rp
                self.rank[rp] += 1
    
    def find(self, p):
        root = p
        while self.parent[root] != root:
            root = self.parent[root]
        while p != root:
            next_p = self.parent[p]
            self.parent[p] = root
            p = next_p
        return root


print("=" * 60)
print("PATH COMPRESSION ADIM ADIM")
print("=" * 60)

# Uzun bir zincir oluştur (worst case)
uf = UnionFindVerbose(8)

# Yapay olarak uzun zincir oluştur
uf.parent = [1, 2, 3, 4, 5, 6, 7, 7]
# 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7

print("\nBaşlangıç (uzun zincir):")
print(f"parent[]: {uf.parent}")
print("""
Ağaç yapısı:
    7
    |
    6
    |
    5
    |
    4
    |
    3
    |
    2
    |
    1
    |
    0
""")

print("─" * 60)
print("find(0) çağrısı:")
print("─" * 60)
root = uf.find_verbose(0)

print(f"\nSONRA:")
print(f"parent[]: {uf.parent}")
print("""
Ağaç yapısı:
        7
    /||||||\\ 
   0 1 2 3 4 5 6

Tüm düğümler artık doğrudan root'a bağlı!
""")

print("─" * 60)
print("find(0) tekrar çağrılırsa:")
print("─" * 60)
root = uf.find_verbose(0)
print("\n→ Tek adımda root'a ulaştık!")

import time
import random

class QuickFind:
    def __init__(self, n):
        self.id = list(range(n))
        self.n = n
    def find(self, p): return self.id[p]
    def union(self, p, q):
        pid, qid = self.id[p], self.id[q]
        if pid != qid:
            for i in range(self.n):
                if self.id[i] == pid: self.id[i] = qid

class QuickUnion:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, p):
        while self.parent[p] != p: p = self.parent[p]
        return p
    def union(self, p, q):
        rp, rq = self.find(p), self.find(q)
        if rp != rq: self.parent[rp] = rq

class WeightedQU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, p):
        while self.parent[p] != p: p = self.parent[p]
        return p
    def union(self, p, q):
        rp, rq = self.find(p), self.find(q)
        if rp != rq:
            if self.size[rp] < self.size[rq]: rp, rq = rq, rp
            self.parent[rq] = rp
            self.size[rp] += self.size[rq]

class WeightedQUPC:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, p):
        root = p
        while self.parent[root] != root: root = self.parent[root]
        while p != root:
            next_p = self.parent[p]
            self.parent[p] = root
            p = next_p
        return root
    def union(self, p, q):
        rp, rq = self.find(p), self.find(q)
        if rp != rq:
            if self.rank[rp] < self.rank[rq]: rp, rq = rq, rp
            self.parent[rq] = rp
            if self.rank[rp] == self.rank[rq]: self.rank[rp] += 1


def benchmark(UFClass, n, m, seed=42):
    random.seed(seed)
    pairs = [(random.randint(0, n-1), random.randint(0, n-1)) for _ in range(m)]
    
    start = time.time()
    uf = UFClass(n)
    for p, q in pairs:
        uf.union(p, q)
    for p, q in pairs[:m//2]:
        uf.find(p)
    elapsed = time.time() - start
    return elapsed


print("=" * 70)
print("PERFORMANS KARŞILAŞTIRMASI")
print("=" * 70)

print(f"\n{'Algoritma':<25} {'N=1000':<12} {'N=5000':<12} {'N=10000':<12}")
print("-" * 70)

algorithms = [
    ("Quick-Find", QuickFind),
    ("Quick-Union", QuickUnion),
    ("Weighted QU", WeightedQU),
    ("WQU + Path Compression", WeightedQUPC),
]

for name, UFClass in algorithms:
    times = []
    for n in [1000, 5000, 10000]:
        t = benchmark(UFClass, n, n)
        times.append(f"{t:.4f}s")
    print(f"{name:<25} {times[0]:<12} {times[1]:<12} {times[2]:<12}")

print("\n" + "─" * 70)
print("💡 Gözlemler:")
print("─" * 70)
print("""
1. Quick-Find ve Quick-Union: N arttıkça süre HIZLA artıyor (quadratic)
2. Weighted QU: Çok daha hızlı (logarithmic)
3. WQU + PC: En hızlı! (neredeyse sabit)

Büyük N için fark DRAMATIK:
- N = 1,000,000 olsa, Quick-Find dakikalarca sürer
- WQU + PC saniyeler içinde biter
""")