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

Система непересекающихся множеств: как это работает?

Каждый элемент начинается своей группой. Его указатель ведёт на себя.

find поднимается по цепочке родителей до корня. Корень и есть имя группы.

union берёт два элемента, находит оба корня и вешает один под другой. Один вызов сливает две группы.

Сжатие пути переписывает узлы на пути прямо на корень. Следующий find делает один шаг.

Ранговое объединение вешает низкое дерево под высокое. Так цепочки не растут.

С обоими приёмами find и union стоят почти константу. Рёбра при этом нигде не хранятся.

1. [0, 1, 2, 3, 4]Пять элементов, пять групп. Каждый сам себе родитель.
2. [0, 0, 2, 3, 4]union(0, 1) вешает 1 под 0. У двух элементов общий корень.
3. [0, 0, 2, 2, 4]union(2, 3) вешает 3 под 2. Появилась вторая группа.
4. [0, 0, 0, 2, 4]union(1, 2) находит корни 0 и 2. Корень 2 уходит под корень 0.
5. [0, 0, 0, 0, 4]find(3) идёт 3, 2, 0. Сжатие ставит 3 сразу на 0.

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;
    }
}

Система непересекающихся множеств: разбор примера

Лишнее ребро

Дан граф, который был деревом, плюс одно лишнее ребро. Найдите ребро, замыкающее цикл.

Рёбра приходят по порядку. Верните последнее, соединяющее уже связанные вершины.

Идите по рёбрам подряд и объединяйте концы.

Если у концов уже общий корень, ребро ничего не добавляет. Оно замыкает цикл.

Запоминайте последнее такое ребро. Это и есть ответ.

function findRedundantConnection(edges) {
    const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);

    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    let answer = [];
    for (const [a, b] of edges) {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA === rootB) {
            answer = [a, b]; // both ends were already connected
        } else {
            parent[rootA] = rootB;
        }
    }

    return answer;
}

Система непересекающихся множеств: когда применять?

Эти формулировки в условии ведут сюда:

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

Система непересекающихся множеств: с чем путают?

• Компоненты связности (Connected components): Заливка считает группы в уже готовом графе. Здесь ответ нужен, пока рёбра ещё приходят.
• Обход графа в ширину и глубину (Graph BFS / DFS): Обход ходит по соседям, значит нужен список смежности. Здесь рёбра не хранятся совсем.
• Топологическая сортировка (Topological sort (Kahn's algorithm)): Топологический порядок требует направленных рёбер без циклов. Здесь любое ребро ненаправленное.
• Хеш-таблица и множество (Hash set / map): Словарь группирует по заранее известному ключу. Здесь группы выясняются по мере слияний.

Система непересекающихся множеств: частые ошибки

• Сравнивают элементы, а не корни

  Два элемента одной группы могут иметь разных родителей. Сравнивайте find(a) и find(b).

• union без find

  Запись parent[a] = b соединяет два элемента, а не две группы. Вешайте всегда корень под корень.

• Пропускают сжатие пути

  Без него цепочка вырастает до n звеньев. Один find тогда стоит O(n).

• Размер массива берут по числу рёбер

  Массив индексируется элементами, а не рёбрами. Ошибка на единицу даёт undefined на последней вершине.

Система непересекающихся множеств: задачи с собеседований

• Число провинций: Объедините все связанные пары и посчитайте разные корни.
• Лишнее ребро: Первое ребро, у концов которого уже общий корень.
• Слияние аккаунтов: Почты связывают аккаунты. Объединяйте по общей почте, потом группируйте по корню.
• Число островов: Объединяйте соседние клетки суши. Удобно, когда сетка приходит частями.
• Максимум убранных камней: Камни в одной строке или колонке образуют группу.
• Выполнимость равенств: Сначала объедините равенства. Потом проверьте каждое неравенство по корням.
• Наименьшая строка обменами: Обмениваемые индексы образуют группу. Отсортируйте буквы внутри каждой группы.

Система непересекающихся множеств: сложность по времени и памяти

near O(1) per op

n до 1e6 элементов и m перемешанных запросов дают O(m alpha(n)). Alpha меньше 5 при любом реальном n.