మార్గ కంప్రెషన్ మరియు ర్యాంక్ ద్వారా యూనియన్ కలిగిన డిస్జాయింట్-సెట్ (యూనియన్-ఫైండ్) స్ట్రక్చర్ అంటే ఏమిటి?

Question

IT Interview Practice · Accepted Answer

**డిస్జాయింట్-సెట్** (యూనియన్-ఫైండ్) నాన్-ఓవర్‌లాపింగ్ గ్రూపులుగా విభజించిన మూలకాలను ట్రాక్ చేస్తుంది మరియు "**ఈ ఇద్దరు ఒకే గ్రూపులో ఉన్నారా?**" మరియు "**రెండు గ్రూపులను విలీనం చేయండి**" అనే ప్రశ్నలకు **సుమారు-స్థిరమైన సమయం**లో సమాధానం ఇస్తుంది. **మార్గ కంప్రెషన్** మరియు **ర్యాంక్ ద్వారా యూనియన్** ఉన్నప్పుడు, రెండు ఆపరేషన్‌లు **O(α(n))** లో నడుస్తాయి — ప్రభావంగా O(1) (α విలోమ అకర్‌మన్ ఫంక్షన్)।

## ఇది ఎలా కार్యం చేస్తుంది

ప్రతిটి సెట్ ఒక చెట్టు; **రూట్** సెట్ యొక్క ప్రతినిధి. `find` రూట్‌కు నడుస్తుంది; `union` ఒక రూట్‌ను మరొకటి క్రింద అనుసంధానం చేస్తుంది।

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## కోడ్

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        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
        return True
```

| ఆపరేషన్ | సమయం (రెండు ఆప్టిమైజేషన్‌ల ద్వారా) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## సాధారణ ఉపయోగాలు

- **క్రుస్కల్ MST** — చక్రాలను ఏర్పరచకుండా భాగాలను విలీనం చేయండి.
- **కనెక్ట్ చేయబడిన భాగాలు** గ్రాఫ్ లేదా గ్రిడ్‌లో.
- **డైనమిక్ కানెక్టివిటీ** మరియు నెట్‌వర్క్/పెర్‌కోలేషన్ సమస్యలు.

## ఇది ఎందుకు ముఖ్యమైనది

యూనియన్-ఫైండ్ సమూహం మరియు కానెక్టివిటీ సమస్యలను పరిష్కరిస్తుంది, వేరే విధంగా పునరావృత్తమయ్యే O(n) గ్రాఫ్ ట్రావర్సల్‌లను అవసరం చేస్తుంది, వాటిని ప్రతి ప్రశ్నకు సుమారు O(1)కు సంపీడనం చేస్తుంది।

సెట్‌లను క్రమంగా విలీనం చేయాలి మరియు కానెక్టివిటీని పరీక్షించాల్సిన ప్రతిసారీ ఇది ఎలుకకు సరిపోయే సాధనం — సీనియర్-లెవల్ ఇంటర్‌వ్యూ విషయం.

ఇది ఎలా కार్యం చేస్తుంది

కోడ్

సాధారణ ఉపయోగాలు

ఇది ఎందుకు ముఖ్యమైనది

సంబంధిత ప్రశ్నలు