Çfarë është struktura e ndarjes-bashkimit (union-find) me ngjeshjen e rrugës dhe bashkimin sipas rangut?

Question

IT Interview Practice · Accepted Answer

Një **ndarje-bashkim** (union-find) ndjek elementet e ndarë në grupe jo-mbivendosje dhe përgjigjet "**a janë këto dy në të njëjtën grup?**" dhe "**bashko dy grupe**" në **kohë pothuajse konstante**. Me **ngjeshjen e rrugës** dhe **bashkimin sipas rangut**, të dyja operacionet funksionojnë në **O(α(n))** — praktikisht O(1) (α është funksioni invers Ackermann).

## Si funksionon

Çdo bashkim është një pemë; **rrënja** është përfaqësuesi i bashkimit. `find` shkon në rrënjën e pemës; `union` lidh një rrënjë nën tjetrën.

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

## Kodi

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

| Operacioni | Koha (me të dyja optimizimeve) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Përdorimet e zakonshme

- **MST i Kruskalit** — bashko komponentet pa formuar cikle.
- **Komponentet e lidhura** në një graf ose rrjet.
- **Lidhja dinamike** dhe problemet e rrjetit/perkolimit.

## Pse është i rëndësishëm

Union-find zgjidh problemet e bashkimit dhe lidhjes që ndryshe do të kishin nevojë për kalime të përsëritur O(n) grafesh, dhe i bën ato pothuajse O(1) për kërkesë.

Është një mjet themelor kur duhet të bashkosh hap pas hapi bashkime dhe të kontrollosh lidhjen — një temë e shpeshtë në intervjuet për nivelin senior.

Si funksionon

Kodi

Përdorimet e zakonshme

Pse është i rëndësishëm

Pyetje të ngjashme