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

Структура данных DSU с эвристиками сжатия путей и объединения по рангу. Амортизированное время работы O(α(N)), где α — обратная функция Аккермана.

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

DSU: предварительные знания, план уроков и практика →

Реализация DSU с оптимизациями

cpp

struct DSU {
    vector<int> parent, rank;
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); // Сжатие путей
    }
    bool unite(int i, int j) {
        int root_i = find(i), root_j = find(j);
        if (root_i != root_j) {
            if (rank[root_i] < rank[root_j]) swap(root_i, root_j);
            parent[root_j] = root_i;
            if (rank[root_i] == rank[root_j]) rank[root_i]++;
            return true;
        }
        return false;
    }
};

Что дальше?

Закрепите материал задачей: Повторить число.

Изучено — к практике →

Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».