Определение

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

СНМ часто называют DSU, от англ. Disjoint Set Union, хотя DSU - это название только операции объединения (Union). Впрочем, эта аббревиатура уже устоялась в олимпиадном программировании, поэтому она будет использоваться далее.

DSU представляет собой набор корневых деревьев (лес). Каждое дерево соответствует определённому множеству. При реализации DSU необходимо лишь подниматься вверх по деревьям, поэтому достаточно хранить для каждой вершины только номер её прямого предка. Для этого используется массив \(p\).

Для описания множества используется номер вершины, являющейся корнем соответствующего дерева. Поэтому для определения, принадлежат ли два элемента к одному и тому же множеству, для каждого элемента нужно найти корень соответствующего дерева (поднимаясь вверх пока это возможно) и сравнить эти корни.

Объединяются множества элементарно. Пусть нам нужно объединить множества с корнями \(a\) и \(b\). Просто присвоим \(p[a] = b\), тем самым подвесив всё дерево \(a\) к корню дерева \(b\).

Реализация: наивный вариант

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int p[100000];

void init_dsu() {
    for (int i = 0; i < 100000; i++) {
        p[i] = i;  //каждая вершина изначально является корнем отдельного дерева
    }
}

int get_root(int v) {
    if (p[v] == v) {
        return v;
    } else {
        return get_root(p[v]);
    }
}

//a и b - любые вершины в деревьях
//возвращаемое значение обозначает, находились ли до вызова функции a и b в разных деревьях
bool merge(int a, int b) {
    int ra = get_root(a), rb = get_root(b);

    if (ra == rb) {
        return false;
    } else {
        p[ra] = rb;
        return true;
    }
}

При такой реализации создаётся 100000 вершин, каждая из которых является отдельным деревом.

Оптимизация 1: ранги вершин

Можно заметить, что при такой реализации при постепенном объединении деревьев глубина будет расти вплоть до \(N\), так как деревья вырождаются в связные списки. Разумеется, такая глубина не позволяет эффективно использовать структуру данных. Поэтому нужно применять дополнительные оптимизации, в первую очередь, при объединении деревьев.

Одна из самых простых и эффективных оптимизаций - поддерживать для всех деревьев текущую глубину, и при объединении подвешивать дерево с меньшей глубиной к корню дерева с большей глубиной. Глубина дерева данной вершины поддерживается в виде её ранга. Строго говоря, при применении дополнительной оптимизации (описанной ниже), ранг вершины описывают не точную глубину дерева, а её верхнюю границу, но это не играет роли.

Реализация: ранги вершин

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

int p[100000];
int rk[100000];   //имя rank уже используется библиотекой

void init_dsu() {
    for (int i = 0; i < 100000; i++) {
        p[i] = i;
        rk[i] = 1;    //Начальное значение не играет роли.
    }
}

int get_root(int v) {
    if (p[v] == v) {
        return v;
    } else {
        return get_root(p[v]);
    }
}

bool merge(int a, int b) {
    int ra = get_root(a), rb = get_root(b);

    if (ra == rb) {
        return false;
    } else {
        if (rk[ra] < rk[rb]) {
            p[ra] = rb;
        } else if (rk[rb] < rk[ra]) {
            p[rb] = ra;
        } else {            //Если оба дерева имеют одинаковую глубину,
            p[ra] = rb;     //неважно, какое из них подвешивать.
            rk[rb]++;     //При этом глубина нового дерева увеличится на 1.
        }

        return true;
    }
}

Оптимизация 2: сжатие путей

С помощью рангов максимальная глубина дерева (а значит и сложность операций) понизилась до \(\log N\). Этого уже может быть достаточно, но существует ещё одна невероятно простая оптимизация (для её применения достаточно добавить в предущий код пять символов). Эта оптимизация заключается в сжатии путей при поиске корня.

Идея заключается в следующем: при поиске корня заданной вершины будем переподвешивать её за найденный корень. Допустим, мы вызвали функцию get_root для вершины, которую отделяют от корня дерева пять других вершин. Рекурсивный вызов get_root обойдёт каждую из них, и найдёт корень. На выходе из каждого рекурсивного вызова просто переподвесим текущую вершину за только что найденный корень. Таким образом, все пять вершин теперь будут подвешены напрямую к корню.

Реализация: сжатие путей

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

int p[100000];
int rk[100000];

void init_dsu() {
    for (int i = 0; i < 100000; i++) {
        p[i] = i;
        rk[i] = 1;
    }
}

int get_root(int v) {
    if (p[v] == v) {
        return v;
    } else {
        return p[v] = get_root(p[v]);   //На выходе из рекурсии переподвешиваем v
    }
}

bool merge(int a, int b) {
    int ra = get_root(a), rb = get_root(b);

    if (ra == rb) {
        return false;
    } else {
        if (rk[ra] < rk[rb]) {
            p[ra] = rb;
        } else if (rk[rb] < rk[ra]) {
            p[rb] = ra;
        } else {
            p[ra] = rb;
            rk[rb]++;
        }

        return true;
    }
}

При такой реализации амортизированная сложность каждой операции равна \(O(\alpha(n))\), где \(\alpha(n)\) - обратная функция Аккермана, значение которой не превышает \(5\) для всех разумных \(n\). Другими словами, амортизированная сложность каждой операции примерно равна \(O(1)\).

Под амортизированной сложностью подразумевают отношение времени работы алгоритма ко входным данным в большинстве случаев (не учитываются, в частности, сжатия путей, которые происходят достаточно редко).

Применение DSU

Чаще всего DSU используется вместе с алгоритмом Крускала для нахождения минимального остовного дерева графа.