Union-find কী এবং এটি কোথায় ব্যবহার করা হয়?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) উপাদানগুলিকে **disjoint sets**-এ বিভাজন ট্র্যাক করে এবং দুটি near-O(1) অপারেশন সমর্থন করে: **find** (x কোন সেটে আছে?) এবং **union** (দুটি সেট মার্জ করুন)। এটি **connectivity** queries-এ উৎকর্ষ লাভ করে।

## The idea

প্রতিটি সেট একটি প্রতিনিধিত্বকারী রুটের সাথে একটি গাছ। **path compression** এবং **union by rank/size** সহ, অপারেশনগুলি প্রায় ধ্রুবক **amortized** সময়ে চলে (inverse Ackermann, α(n))।

## Example

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # compress
            x = self.parent[x]
        return x
    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           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## Complexity

- **find / union:** O(α(n)) ≈ O(1) amortized। **Space:** O(n)।

## Applications

- **Kruskal's MST** — edge যোগ করার সময় cycle detection।
- **Connected components** / dynamic connectivity।
- **Cycle detection** undirected graphs-এ।
- **Percolation**, image segmentation, account/network merging।

## Pitfalls

path compression এবং union by rank ছাড়া, গাছগুলি O(n) chains-এ অবনত হয়। এটি সেটগুলির দক্ষ *splitting* সমর্থন করে না।

## Why it matters

Union-find "এই দুটি জিনিস কি সংযুক্ত?" প্রশ্নের উত্তর বিশাল স্কেলে প্রায় কোনো খরচ ছাড়াই দেয়।

এটি Kruskal's MST এবং অনেক graph এবং clustering algorithms-এর ইঞ্জিন।

এর দুটি optimization ছোট structural tricks কীভাবে near-constant-time performance প্রদান করে তার একটি স্মরণীয় পাঠ।