Union-Find (DSU)

O(α(n)) per op

Union-Find (sjednocení disjunktních množin) udržuje kolekci disjunktních množin, tady nakreslených jako les, kde každá množina je strom a jeho kořen je reprezentant. find(x) sleduje ukazatele na rodiče až ke kořeni; union(a, b) připojí kořen jednoho stromu pod druhý. Dvě optimalizace z toho dělají skoro O(1) na operaci (inverzní Ackermann, α(n)): sjednocení podle velikosti vždy připojí menší strom pod větší, aby stromy zůstaly mělké, a komprese cesty přepojí každý uzel navštívený při find rovnou na kořen a strom tím zploští pro příště. Stojí za Kruskalovou MST, komponentami souvislosti, detekcí cyklů i segmentací obrazu. Kořeny mají kroužek; aktivní cesta find je teal.

u a b = sjednoť · f a = najdi (0–9)
Les disjunktních množin
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Každý prvek začíná jako vlastní jednouzlová množina (vlastní kořen).
  2. find(x) vyjde po ukazatelích na rodiče ke kořeni a pak zkomprimuje cestu.
  3. union(a, b) najde oba kořeny a připojí menší strom pod větší.
  4. Sjednocení prvků už ve stejné množině nic nezmění.

Pseudokód

1unionFind:                          # ~O(1) amortised per op2  parent[i] = i, size[i] = 1        # n singleton sets3  find(x): follow parent to the root,4           then point the path straight at it  # path compression5  union(a, b): r1 = find(a), r2 = find(b)6    attach the smaller tree under the larger    # union by size