Cad is struchtúr disjoint-set (union-find) le dhíchomhbhrú cosáin agus aontas de réir ní gnoíochta?

Question

Accepted Answer

Rianaíonn **struchtúr disjoint-set** (union-find) na heilimintí roinnte i ngrúpaí neamhthrasnaithe agus tugann sé freagra ar "**an bhfuil an dá rud seo sa ghrúpa céanna?**" agus "**dhá ghrupaí a shuathadh**" in **am gar-tairiseach**. Le **díchomhbhrú cosáin** agus **aontas de réir ní gnoíochta**, ritheann an dá oibríochta in **O(α(n))** — éifeachtúil O(1) (α an fheidhm droim ar ais Ackermann).

## Conas a oibríonn sé

Is crann a bhíonn i ngach tacar; is ionann an **fréamh** agus ionadaí an tacair. Siúlann `find` go dtí an fréamh; nascann `union` fréamh amháin faoin cheann eile.

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

## Cód

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

| Oibríochta | Am (leis an dá bharrfheidhmiú) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Úsáidí coitianta

- **MST Kruskal** — comhpháirteanna a shuathadh gan timthriallta a dhéanamh.
- **Comhpháirteanna ceangailte** i ngraf nó eangach.
- **Nascacht dhinimic** agus fadhbanna gréasáin/imfhilleadh.

## Cén fáth a bhfuil sé tábhachtach

Réitíonn union-find fadhbanna grúpála agus nascachta a bhainfeadh, ar dhóigh eile, le trasnaithe graf O(n) athrá, agus iad á laghdú go beagnach O(1) in aghaidh an iarratais.

Is uirlis riachtanach a bhíonn ann i gcónaí nuair a chaithfidh tú tacair a shuathadh go céimniúil agus nascacht a thástáil — topaice agallamh minic ar leibhéal sinsir.