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

near O(1) per op

Даём каждому элементу указатель на родителя; поднимаясь по родителям, доходим до корня, который и называет группу. find поднимается к корню, union соединяет два корня, а сжатие пути и объединение по рангу держат обе операции почти на O(1).

Сигналы

в одной ли группе эти два элементафакты о слиянии приходят по одномудинамическая связность по мере добавления рёберслияние аккаунтов/друзей со временемдобавление этого ребра создаст цикл

Шаблон

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        const rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
        else { this.parent[ry] = rx; this.rank[rx]++; }
        return true;
    }
}

Похоже, но не то

Компоненты связности: Union-find отвечает 'одна ли это группа?', пока рёбра прибывают по одному, вперемешку со слияниями. Заливка компонент связности предполагает, что весь граф зафиксирован ещё до начала подсчёта.

n до 1e5..1e6 элементов, m запросов union/find вперемешку во времени -> O(m alpha(n)) суммарно, где alpha - почти постоянная обратная функция Аккермана.

Изучить этот паттерн