Система непересекающихся множеств (DSU)

DSU (union-find, система непересекающихся множеств) поддерживает разбиение элементов на группы и быстро отвечает, лежат ли два элемента в одной группе, а также объединяет группы. С оптимизациями сжатие путей и объединение по рангу операции выполняются практически за константу.

Сложность: find и union — амортизированно O(α(n)) (обратная функция Аккермана, практически O(1)). Память: O(n). Применяется в алгоритме Краскала и поиске компонент связности.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        self.parent[self.find(a)] = self.find(b)