ডাইনামিক অ্যারে ও পাথ-কম্প্রেশনসহ ইউনিয়ন-ফাইন্ড

import random

def naive_uf_run(n, ops):
    """কোনো অপ্টিমাইজেশন ছাড়া ইউনিয়ন-ফাইন্ড: প্লেইন প্যারেন্ট পয়েন্টার,
    কোনো পাথ কম্প্রেশন নেই, কোনো ইউনিয়ন-বাই-র‍্যাংক নেই।"""
    parent = list(range(n))
    total_hops = 0
    total_finds = 0

    def find(x):
        nonlocal total_hops, total_finds
        hops = 0
        while parent[x] != x:
            x = parent[x]
            hops += 1
        total_hops += hops
        total_finds += 1
        return x

    for kind, a, b in ops:
        if kind == 'find':
            find(a)
        else:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb   # নেইভ: সবসময় a-এর রুটকে b-এর রুটের নিচে বসানো
    return total_hops, total_finds


def optimized_uf_run(n, ops):
    """পাথ কম্প্রেশন + ইউনিয়ন বাই র‍্যাংক দুটোসহ ইউনিয়ন-ফাইন্ড।"""
    parent = list(range(n))
    rank = [0] * n
    total_hops = 0
    total_finds = 0

    def find(x):
        nonlocal total_hops, total_finds
        hops = 0
        root = x
        while parent[root] != root:
            root = parent[root]
            hops += 1
        total_hops += hops
        total_finds += 1
        # পাথ কম্প্রেশন: x থেকে root পর্যন্ত সব নোডকে সরাসরি root-এর দিকে নির্দেশ করানো
        while parent[x] != root:
            nxt = parent[x]
            parent[x] = root
            x = nxt
        return root

    for kind, a, b in ops:
        if kind == 'find':
            find(a)
        else:
            ra, rb = find(a), find(b)
            if ra != rb:
                if rank[ra] < rank[rb]:
                    ra, rb = rb, ra
                parent[rb] = ra   # ছোট র‍্যাংকের গাছকে বড় র‍্যাংকের রুটের নিচে বসানো
                if rank[ra] == rank[rb]:
                    rank[ra] += 1
    return total_hops, total_finds


random.seed(42)
num_elems = 300
num_ops = 3000
ops = []
for _ in range(num_ops):
    a = random.randrange(num_elems)
    b = random.randrange(num_elems)
    kind = 'union' if random.random() < 0.5 else 'find'
    ops.append((kind, a, b))

naive_hops, naive_finds = naive_uf_run(num_elems, ops)
opt_hops, opt_finds = optimized_uf_run(num_elems, ops)

naive_avg = naive_hops / naive_finds
opt_avg = opt_hops / opt_finds

print(f"এলিমেন্ট সংখ্যা: {num_elems}, মোট অপারেশন: {num_ops}, মোট find কল: {naive_finds}")
print(f"\nনেইভ (কোনো অপ্টিমাইজেশন নেই):")
print(f"  মোট hop: {naive_hops}, গড় hop/find: {naive_avg:.4f}")
print(f"\nঅপ্টিমাইজড (পাথ কম্প্রেশন + ইউনিয়ন বাই র‍্যাংক):")
print(f"  মোট hop: {opt_hops}, গড় hop/find: {opt_avg:.4f}")
print(f"\nস্পিডআপ (নেইভ/অপ্টিমাইজড): {naive_avg / opt_avg:.2f}x")