Union-Find — disjoint set-এর inverse Ackermann magic

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

    def find(self, x):
        root = x
        while self.parent[root] != root:       # পাস ১: root খোঁজা
            root = self.parent[root]
        while self.parent[x] != root:          # পাস ২: পথ সমতল
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                       # already connected
        if self.rank[ra] \< self.rank[rb]:
            ra, rb = rb, ra                    # ছোট বড়ের নিচে
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1                 # tie-তেই height বাড়ে
        self.count -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


def max_depth(d):
    """diagnostic: সবচেয়ে গভীর parent-chain"""
    worst = 0
    for x in range(len(d.parent)):
        cur, depth = x, 0
        while d.parent[cur] != cur:
            cur = d.parent[cur]; depth += 1
        worst = max(worst, depth)
    return worst


if __name__ == '__main__':
    N = 100_000

    # --- adversarial chain: union(i, i-1) sequentially ---
    d = DSU(N)
    for i in range(1, N):
        d.union(i, i - 1)
    assert d.count == 1
    assert d.connected(0, N - 1)
    print('chain OK; max depth:', max_depth(d))

    d.find(0); d.find(N - 1)                   # দুই find-ই flatten করে
    print('after finds  :', max_depth(d))

    # --- random invariant suite ---
    import random
    random.seed(5)
    e = DSU(1000)
    for _ in range(2000):
        a, b = random.randrange(1000), random.randrange(1000)
        before = (e.connected(a, b), e.count)
        changed = e.union(a, b)
        after = (e.connected(a, b), e.count)
        assert before[0] or changed            # connected হলে union no-op
        if not before[0]:
            assert after[0] and after[1] == before[1] - 1
        else:
            assert after[1] == before[1]
    print('random invariant suite OK')

প্রত্যাশিত output:

chain OK; max depth: 1
after finds  : 1
random invariant suite OK

Adversarial chain-টা খেয়াল করুন: union(i, i−1) naive-কে দিলে নিশ্চিত n−1-level chain; rank-guarded version-এ max depth ১ (প্রতিটা নতুন i singleton — সবসময় smaller-under-larger, star হয়ে যায়)। Production bug-hunt- এ প্রথম যে fingerprint খোঁজা হয়, এটাই।

নিজে বাড়ান: (১) permutation-parity variant — edge-XOR weight accumulate find-এ, rewrite compression-এ; even/odd swap-cycle বলে দেবে; (২) rollback DSU (history stack + undo); (৩) path-halving one-pass (parent[x] = parent[parent[x]]) লিখে two-pass benchmark।