Система непересекающихся множеств (DSU/Union-Find): полное руководство

Что такое DSU (Union-Find)?

Система непересекающихся множеств (Disjoint Set Union, DSU) — это структура данных, которая поддерживает:

• Find(x) — найти представителя множества, содержащего элемент x
• Union(x, y) — объединить множества, содержащие x и y

Зачем нужен DSU?

DSU идеально подходит для задач на связность:

• Есть ли путь между двумя вершинами в графе?
• Сколько компонент связности?
• Когда граф становится связным при добавлении рёбер?

α(n) — обратная функция Аккермана, практически константа (≤ 4 для всех разумных n).

Принцип работы

Каждое множество представляется как дерево:

• Корень дерева — представитель множества
• Каждый элемент хранит ссылку на родителя

Визуализация

Изначально: каждый элемент — отдельное множество

{1}  {2}  {3}  {4}  {5}

 1    2    3    4    5   (каждый указывает на себя)

После Union(1, 2) и Union(3, 4):

{1, 2}  {3, 4}  {5}

  1       3
  |       |
  2       4       5

После Union(2, 4):

{1, 2, 3, 4}  {5}

      1
     / \
    2   3
        |
        4         5

Базовая реализация (без оптимизаций)

JavaScript

class DSU {
    constructor(n) {
        // parent[i] = родитель элемента i
        // Изначально каждый элемент — сам себе родитель
        this.parent = Array.from({ length: n }, (_, i) => i);
    }

    // Найти корень (представителя) множества
    find(x) {
        if (this.parent[x] !== x) {
            return this.find(this.parent[x]);
        }
        return x;
    }

    // Объединить множества, содержащие x и y
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX !== rootY) {
            this.parent[rootX] = rootY;
        }
    }

    // Проверить, в одном ли множестве x и y
    connected(x, y) {
        return this.find(x) === this.find(y);
    }
}

// Пример
const dsu = new DSU(5);
dsu.union(0, 1);
dsu.union(2, 3);
console.log(dsu.connected(0, 1)); // true
console.log(dsu.connected(0, 2)); // false
dsu.union(1, 3);
console.log(dsu.connected(0, 2)); // true

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Python

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            self.parent[root_x] = root_y

    def connected(self, x, y):
        return self.find(x) == self.find(y)


# Пример
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(2, 3)
print(dsu.connected(0, 1))  # True
print(dsu.connected(0, 2))  # False
dsu.union(1, 3)
print(dsu.connected(0, 2))  # True

Проблема: В худшем случае дерево вырождается в цепочку → O(n) на find!

Оптимизация 1: Сжатие путей (Path Compression)

Идея: При вызове find(x) перенаправляем все узлы на пути напрямую к корню.

До:          После find(4):
    1              1
    |           /  |  \
    2          2   3   4
    |
    3
    |
    4

Реализация

find(x) {
    if (this.parent[x] !== x) {
        // Рекурсивно находим корень и обновляем parent
        this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
}

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

Амортизированная сложность: O(log n) на операцию.

Оптимизация 2: Ранговая эвристика (Union by Rank)

Идея: При объединении присоединяем меньшее дерево к большему.

Ранг — верхняя оценка высоты дерева.

class DSU {
    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 rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX === rootY) return false;

        // Присоединяем дерево с меньшим рангом к дереву с большим
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            // Ранги равны — выбираем любой и увеличиваем его ранг
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }

        return true;
    }
}

Оптимизация 3: Union by Size

Альтернатива рангу — хранить размер множества:

class DSU {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.size = new Array(n).fill(1);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX === rootY) return false;

        // Присоединяем меньшее множество к большему
        if (this.size[rootX] < this.size[rootY]) {
            this.parent[rootX] = rootY;
            this.size[rootY] += this.size[rootX];
        } else {
            this.parent[rootY] = rootX;
            this.size[rootX] += this.size[rootY];
        }

        return true;
    }

    // Получить размер множества, содержащего x
    getSize(x) {
        return this.size[this.find(x)];
    }
}

Python версия с обеими оптимизациями

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n
        self.components = n  # Количество компонент

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Сжатие путей
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False

        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]

        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        self.components -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]

    def get_components(self):
        return self.components

Сложность с оптимизациями

α(n) — обратная функция Аккермана:

• α(10^80) ≈ 4
• Практически константа для любых реальных данных

Применение DSU

Задача 1: Количество компонент связности

function countComponents(n, edges) {
    const dsu = new DSU(n);

    for (const [u, v] of edges) {
        dsu.union(u, v);
    }

    // Считаем уникальные корни
    const roots = new Set();
    for (let i = 0; i < n; i++) {
        roots.add(dsu.find(i));
    }

    return roots.size;
}

// Или с использованием счётчика
class DSU {
    // ... предыдущий код ...

    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.count = n; // Количество компонент
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX === rootY) return false;

        // ... объединение ...

        this.count--; // Уменьшаем счётчик при объединении
        return true;
    }

    getCount() {
        return this.count;
    }
}

Задача 2: Redundant Connection (LeetCode 684)

Найти ребро, удаление которого превратит граф в дерево:

def find_redundant_connection(edges):
    n = len(edges)
    dsu = DSU(n + 1)

    for u, v in edges:
        if not dsu.union(u, v):
            # u и v уже в одном множестве — это лишнее ребро
            return [u, v]

    return []

Задача 3: Алгоритм Крускала (MST)

Минимальное остовное дерево:

function kruskal(n, edges) {
    // Сортируем рёбра по весу
    edges.sort((a, b) => a[2] - b[2]);

    const dsu = new DSU(n);
    const mst = [];
    let totalWeight = 0;

    for (const [u, v, weight] of edges) {
        if (dsu.union(u, v)) {
            mst.push([u, v, weight]);
            totalWeight += weight;

            // Остовное дерево содержит n-1 рёбер
            if (mst.length === n - 1) break;
        }
    }

    return { mst, totalWeight };
}

// Пример
const edges = [
    [0, 1, 4],
    [0, 2, 3],
    [1, 2, 1],
    [1, 3, 2],
    [2, 3, 4]
];
console.log(kruskal(4, edges));
// { mst: [[1,2,1], [1,3,2], [0,2,3]], totalWeight: 6 }

Задача 4: Проверка двудольности графа

class BipartiteDSU:
    def __init__(self, n):
        # Для каждой вершины храним её и её "противоположность"
        self.parent = list(range(2 * n))
        self.rank = [0] * (2 * n)

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1


def is_bipartite(n, edges):
    dsu = BipartiteDSU(n)

    for u, v in edges:
        # Если u и v уже в одном множестве — не двудольный
        if dsu.find(u) == dsu.find(v):
            return False

        # u должен быть в противоположной группе от v
        dsu.union(u, v + n)
        dsu.union(v, u + n)

    return True

Задача 5: Accounts Merge (LeetCode 721)

Объединение аккаунтов с общими email:

function accountsMerge(accounts) {
    const emailToId = new Map();
    const emailToName = new Map();
    let id = 0;

    // Присваиваем ID каждому email
    for (const account of accounts) {
        const name = account[0];
        for (let i = 1; i < account.length; i++) {
            const email = account[i];
            if (!emailToId.has(email)) {
                emailToId.set(email, id++);
            }
            emailToName.set(email, name);
        }
    }

    const dsu = new DSU(id);

    // Объединяем email одного аккаунта
    for (const account of accounts) {
        const firstEmail = account[1];
        for (let i = 2; i < account.length; i++) {
            dsu.union(emailToId.get(firstEmail), emailToId.get(account[i]));
        }
    }

    // Группируем email по корню
    const rootToEmails = new Map();
    for (const [email, emailId] of emailToId) {
        const root = dsu.find(emailId);
        if (!rootToEmails.has(root)) {
            rootToEmails.set(root, []);
        }
        rootToEmails.get(root).push(email);
    }

    // Формируем результат
    const result = [];
    for (const [root, emails] of rootToEmails) {
        emails.sort();
        const name = emailToName.get(emails[0]);
        result.push([name, ...emails]);
    }

    return result;
}

Расширения DSU

DSU с откатом (Rollback DSU)

Для задач, где нужно отменять операции union:

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.history = []  # Стек изменений

    def find(self, x):
        # БЕЗ сжатия путей!
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            self.history.append(None)  # Пустая операция
            return False

        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x

        # Сохраняем состояние для отката
        self.history.append((root_y, self.parent[root_y], root_x, self.rank[root_x]))

        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        return True

    def rollback(self):
        if not self.history:
            return

        change = self.history.pop()
        if change is None:
            return

        root_y, old_parent, root_x, old_rank = change
        self.parent[root_y] = old_parent
        self.rank[root_x] = old_rank

Взвешенный DSU

Хранит "расстояние" до корня:

class WeightedDSU {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.diff = new Array(n).fill(0); // diff[x] = x - parent[x]
    }

    find(x) {
        if (this.parent[x] === x) {
            return { root: x, dist: 0 };
        }

        const { root, dist } = this.find(this.parent[x]);
        this.parent[x] = root;
        this.diff[x] += dist;
        return { root, dist: this.diff[x] };
    }

    // Объединить с условием: x - y = w
    union(x, y, w) {
        const { root: rootX, dist: distX } = this.find(x);
        const { root: rootY, dist: distY } = this.find(y);

        if (rootX === rootY) {
            // Проверяем согласованность
            return distX - distY === w;
        }

        // rootX - rootY = (x - distX) - (y - distY) = w - distX + distY
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
            this.diff[rootX] = distY - distX + w;
        } else {
            this.parent[rootY] = rootX;
            this.diff[rootY] = distX - distY - w;
            if (this.rank[rootX] === this.rank[rootY]) {
                this.rank[rootX]++;
            }
        }

        return true;
    }
}

Типичные ошибки

Ошибка 1: Забыли сжатие путей

// Плохо — O(n) в худшем случае
find(x) {
    while (this.parent[x] !== x) {
        x = this.parent[x];
    }
    return x;
}

// Хорошо — O(α(n))
find(x) {
    if (this.parent[x] !== x) {
        this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
}

Ошибка 2: Неправильная индексация

// Если вершины нумеруются с 1
const dsu = new DSU(n + 1); // Не забыть +1!

Ошибка 3: Не проверили, нужно ли объединение

union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    // Обязательно проверить!
    if (rootX === rootY) return false;

    // ... объединение ...
    return true;
}

Сравнение с другими подходами

Задачи для практики

1. Number of Connected Components (LeetCode 323) — базовый DSU
2. Redundant Connection (LeetCode 684) — поиск лишнего ребра
3. Accounts Merge (LeetCode 721) — объединение по общим элементам
4. Satisfiability of Equality Equations (LeetCode 990) — проверка условий
5. Most Stones Removed (LeetCode 947) — подсчёт компонент
6. Regions Cut By Slashes (LeetCode 959) — нестандартное применение

Заключение

DSU — незаменимая структура данных для задач на связность:

• Простота — легко реализовать за 20 строк
• Эффективность — практически O(1) на операцию
• Универсальность — применим к множеству задач

Ключевые оптимизации:

1. Сжатие путей — перенаправление к корню при find
2. Union by rank/size — присоединение меньшего к большему

Рекомендуемый порядок изучения:

1. Базовая реализация
2. Сжатие путей
3. Union by rank
4. Подсчёт компонент
5. Алгоритм Крускала
6. Продвинутые расширения (rollback, weighted)