Τι είναι μια δομή disjoint-set (union-find) με συμπίεση διαδρομής και ένωση κατά κατάταξη;

Question

IT Interview Practice · Accepted Answer

Ένα **disjoint-set** (union-find) παρακολουθεί στοιχεία χωρισμένα σε μη επικαλυπτόμενες ομάδες και απαντά **"είναι αυτά τα δύο στην ίδια ομάδα;"** και **"συγχώνευση δύο ομάδων"** σε **σχεδόν σταθερό χρόνο**. Με **συμπίεση διαδρομής** και **ένωση κατά κατάταξη**, και οι δύο πράξεις εκτελούνται σε **O(α(n))** — πρακτικά O(1) (α είναι η αντίστροφη συνάρτηση Ackermann).

## Πώς λειτουργεί

Κάθε σύνολο είναι ένα δέντρο; η **ρίζα** είναι ο αντιπρόσωπος του συνόλου. `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** — συγχώνευση συστατικών χωρίς σχηματισμό κύκλων.
- **Συνδεδεμένα συστατικά** σε γράφημα ή πλέγμα.
- **Δυναμική συνδεσιμότητα** και προβλήματα δικτύου/διήθησης.

## Γιατί έχει σημασία

Η Union-Find επιλύει προβλήματα ομαδοποίησης και συνδεσιμότητας που διαφορετικά θα απαιτούσαν επανειλημμένες O(n) διαδρομές γραφήματος, καταρρέοντάς τες σε σχεδόν O(1) ανά ερώτημα.

Είναι ένα βασικό εργαλείο κάθε φορά που πρέπει να συγχωνεύσετε σταδιακά σύνολα και να δοκιμάσετε τη συνδεσιμότητα — ένα συχνό θέμα συνέντευξης σε senior level.

Πώς λειτουργεί

Code

Κοινές χρήσεις

Γιατί έχει σημασία

Σχετικές ερωτήσεις