ਡਿਸਜੁਆਇੰਟ-ਸੈੱਟ (union-find) ਢਾਂਚਾ ਪਾਥ ਕੰਪਰੈਸ਼ਨ ਅਤੇ ਯੂਨੀਅਨ ਬਾਈ ਰੈਂਕ ਨਾਲ ਕੀ ਹੈ?

Question

IT Interview Practice · Accepted Answer

ਇੱਕ **disjoint-set** (union-find) ਤੱਤਾਂ ਨੂੰ ਗੈਰ-ਓਵਰਲੈਪਿੰਗ ਗਰੁੱਪਾਂ ਵਿੱਚ ਵੰਡਿਆ ਜਾਂਦਾ ਹੈ ਅਤੇ "**ਕੀ ਇਹ ਦੋ ਇੱਕੋ ਗਰੁੱਪ ਵਿੱਚ ਹਨ?**" ਅਤੇ "**ਦੋ ਗਰੁੱਪਾਂ ਨੂੰ ਮਿਲਾਓ**" ਦੇ ਜਵਾਬ ਦਿੰਦਾ ਹੈ **ਬਹੁਤ ਘੱਟ ਸਮੇਂ ਵਿੱਚ**। **ਪਾਥ ਕੰਪਰੈਸ਼ਨ** ਅਤੇ **ਯੂਨੀਅਨ ਬਾਈ ਰੈਂਕ** ਨਾਲ, ਦੋਨੋਂ ਓਪਰੇਸ਼ਨਜ਼ **O(α(n))** ਵਿੱਚ ਚਲਦੀਆਂ ਹਨ — ਪ੍ਰਭਾਵੀ ਤੌਰ ਤੇ O(1) (α inverse Ackermann function ਹੈ)।

## ਇਹ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ

ਹਰੇਕ ਸੈੱਟ ਇੱਕ ਟ੍ਰੀ ਹੈ; **root** ਸੈੱਟ ਦਾ ਪ੍ਰਸ਼ਤਿਨਿਧ ਹੈ। `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
```

## Code

```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) |

## ਆਮ ਵਰਤੋਂ

- **Kruskal's MST** — ਸਾਈਕਲ ਬਿਨਾਂ ਭਾਗਾਂ ਨੂੰ ਮਿਲਾਓ।
- ਗ੍ਰਾਫ ਜਾਂ ਗ੍ਰਿਡ ਵਿੱਚ **ਜੁੜੇ ਹੋਏ ਭਾਗ**।
- **ਗਤੀਸ਼ੀਲ ਕਨੈਕਟੀਵਿਟੀ** ਅਤੇ ਨੈਟਵਰਕ/percolation ਸਮੱਸਿਆਵਾਂ।

## ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

Union-find ਗਰੁੱਪਿੰਗ ਅਤੇ ਕਨੈਕਟੀਵਿਟੀ ਦੀਆਂ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਹੱਲ ਕਰਦਾ ਹੈ ਜੋ ਬਾਕੀ ਤਰਾਂ ਬਾਰ-ਬਾਰ O(n) ਗ੍ਰਾਫ ਟਰੈਵਰਸਲ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ, ਉਨ੍ਹਾਂ ਨੂੰ ਲਗਭਗ O(1) ਪ੍ਰਤੀ ਪੁੱਛਗਿੱਛ ਵਿੱਚ ਬਦਲ ਦਿੰਦਾ ਹੈ।

ਇਹ ਇੱਕ ਮੁੱਖ ਸਾਧਨ ਹੈ ਜਦੋਂ ਤੁਹਾਨੂੰ ਲਗਾਤਾਰ ਸੈੱਟਾਂ ਨੂੰ ਮਿਲਾਣਾ ਅਤੇ ਕਨੈਕਟੀਵਿਟੀ ਜਾਂਚਣੀ ਹੋਵੇ — ਇੱਕ ਅਕਸਰ ਸੀਨੀਅਰ-ਪੱਧਰ ਦੀ ਸਾਖਾਤਕਾਰ ਵਿਸ਼ੋ।

ਇਹ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ

Code

ਆਮ ਵਰਤੋਂ

ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

ਸੰਬੰਧਿਤ ਸਵਾਲ