Как работает union-find (disjoint set)?

Union-Find (DSU) — структура для efficient tracking disjoint sets. find(x) — representative множества, union(x, y) — объединить. Применения: connected components, Kruskal's MST, cycle detection.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:   # union by rank
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Две оптимизации: path compression (find приподнимает узлы к root) и union by rank (меньшее дерево подвешиваем к большему). С обеими — O(α(n)) amortized per operation, где α — обратная функция Аккермана (практически ≤ 4). LeetCode 547, 684, 721.