# Union-Find / Disjoint Set — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/union-find

> एक structure जो अलग-अलग समूहों को track करता है और 'एक ही समूह?' व 'समूह मिलाएँ' को लगभग O(1) में उत्तर देता है।

## समूह, trees के रूप में

**Union-Find** (Disjoint Set Union) हर समूह को एक tree के रूप में दिखाता है, जहाँ हर node एक `parent` की ओर इशारा करता है, और root अपना ही parent होता है। `find(x)`, x का समूह पहचानने के लिए root तक जाता है; `union(x, y)` एक root को दूसरे के नीचे जोड़ता है।

## Path compression + union by rank

दो optimizations इसे लगभग constant time बना देते हैं: **path compression** `find` के दौरान tree को चपटा करता है, और **union by rank** छोटे tree को बड़े के नीचे जोड़ता है।

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True
```

Output:

```
uf = UnionFind(5)
uf.union(0, 1)
uf.find(0) == uf.find(1)  # True
```

## कहाँ इस्तेमाल होता है

Undirected graph में cycle पहचानना, Kruskal's MST, connected components गिनना, और 'friend circles' जैसी समस्याएँ — सब Union-Find पर निर्भर करती हैं।

## त्वरित जांच

Amortized complexity की समझ परखें।

**Quiz:** Path compression और union by rank के साथ, find/union लगभग चलते हैं:

- [ ] O(n)
- [ ] O(log n)
- [ ] O(n log n)
- [x] लगभग O(1) (inverse-Ackermann)

*Answer:* लगभग O(1) (inverse-Ackermann). Amortized complexity O(α(n)) है, inverse Ackermann function, जो किसी भी वास्तविक n के लिए प्रभावी रूप से स्थिर है।