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

Общие сведения

Система неперескающихся множеств (англ. disjointed set union, иногда union-find) — специфическая структура данных, содержащая информацию о наборе множеств, которая позволяет объединять множества и отвечать на вопрос, принадлежат ли указанные элементы к одному множеству.

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

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

Любое множество может быть уникальным образом идентифицировано с помощью одного из своих элементов: два множества не могут содержать один и тот же элемент по определению (этот факт отражён словом «непересекающихся» в названии структуры данных). Такой элемент называется представителем множества (англ. representative element).

Интерфейс

Здесь и далее будем предполагать, что элементами множеств являются целые числа. Система непересекающихся множеств должна обеспечивать следующие операции:

	int	find(int x)	— определение представителя множества, которому принадлежит элемент x. Очевидно, что если элементы x и y принадлежат одному множеству, то должно выполняться условие find(x) == find(y). В противном случае должно иметь место find(x) != find(y);
	void	merge(int x, int y)	— слияние множеств, содержащих элементы x и y;
	bool	connected(int x, int y)	— определение принадлежности элементов x и y к одному множеству. Из определения метода find() следует, что данный метод в любых реализациях может иметь единый код: return find(x) == find(y);.

Демонстрация работы

• Data Structure Visualizations — Disjoint Sets

В демонстрации элементы-представители содержат ссылки не на самих себя, а на несуществующую ячейку (-1).

• VisuAlgo — Union-Find Disjoint Sets

Простейшая реализация: быстрое определение представителя

Система непересекающихся множеств в простейшей реализации

Определим массив id[], i-ая ячейка которого будет содержать представителя множества, которому принадлежит элемент i.

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

DSU(int n) {
    for (int i = 0; i < n; i++)
        id.push_back(i); //id[i] == i;
}

Определение представителя

Быстрое определение представителя

Как показано выше, массив id[] содержит в своих ячейках значения представителей для всех элементов. Поэтому для вывода представителя в данной реализации достаточно вернуть значение соответствующей ячейки массива id[].

int find(int x) {
    return id[x];
}

Можно видеть, что сложность операции определения представителя в этой реализации — O(1).

Объединение множеств

Объединение множеств в простейшей реализации

После слияния множеств должна сохраняться работоспособность операции find(), то есть все элементы объединённого множества должны иметь одного и того же представителя. Так как до объединения часть элементов имеет представителя a, а другая часть — представителя b, проще всего изменить все упоминания a на b:

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry)
        return;
    for (int i = 0; i < id.size(); i++)
        if (id[i] == rx)
            id[i] = ry;
}

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

Вторая реализация: быстрое объединение

Система непересекающихся множеств: реализация для быстрого объединения

Идея данной реализации в том, что при объединении множеств изменяется лишь один элемент массива id[]. Чтобы это стало возможным, прежде всего необходимо определить несколько условий:

• Теперь элементы множества будут представлены в некоторой многоуровневой древовидной структуре;
• i-ая ячейка массива id[] будет содержать значение элемента, к которому в этой структуре присоединён элемент i;
• Если некоторый элемент i не присоединён к другому элементу, то выполняется id[i] == i. Очевидно, что в каждой древовидной структуре найдётся элемент, обладающий таким свойством — это корень древовидной структуры. Важно, что от любого элемента структуры можно дойти до корневого элемента через некоторое конечное число «подъёмов» по массиву id[]. Эта особенность позволяет использовать корень древовидной структуры в качестве представителя множества.

Конструктор системы непересекающихся множеств остаётся прежним, так как в одноэлементном множестве единственный элемент будет являться корнем и в массиве id[] будет указывать на себя.

DSU(int n) {
    for (int i = 0; i < n; i++)
        id.push_back(i); //id[i] == i;
}

Определение представителя

Определение представителя как корневого элемента

Так как представитель множества — это корень его древовидной структуры, требуется определить именно его. Для этого нужно воспользоваться свойством корня — тем фактом, что он указывает на себя.

int find(int x) {
    if (id[x] == x)
        return x;
    return find(id[x]);
}

Определение представителя в худшем случае следует по массиву id[] от элемента-листа до корня древовидной струтуры, поэтому её сложность прямо пропорциональна высоте древовидной структуры. Ниже показано, что эта сложность составляет O(N).

Объединение множеств

Быстрое объединение множеств

В рассмотренных ограничениях объединение множеств представляет собой объединение их древовидных структур. Для выполнения последнего достаточно присоединить корень одной структуры к элементу другой структуры; в целях минимального увеличения высоты результирующей структуры наиболее выгодно присоединять корень одной из структур к корню другой. Как упоминалось ранее, это потребует корректировки всего одного элемента массива id[]:

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry)
        id[rx] = ry;
}

Несмотря на то, что операция объединения содержит лишь одно обращение к массиву id[], она использует вызовы операции find(), поэтому её сложность также зависит от высоты древовидной структуры. В том случае, когда происходит постоянное подвешивание корня структуры к единственному элементу другой структуры, результат вырождается в односвязный список, а его высота становится равной N. Поэтому операция объединения, равно как операция определения представителя, в данной реализации имеет сложность O(N).

С помощью двух сравнительно простых дополнений скорость работы данной реализации улучшается разительным образом.

Оптимальная реализация

Реализация системы непересекающихся множеств с наилучшим возможным временем работы осуществляется на базе версии «быстрого объединения» с использованием двух дополнительных эвристик (оптимизаций, не имеющих строгого математического обоснования).

Эвристика объединения по рангу

Принцип объединения по рангу

Как было показано ранее, время работы реализации «быстрое объединение» ухудшается с ростом высоты древовидной структуры. Сама же высота может стремительно деградировать до N при неудачно подобранных входных данных (когда структура большего размера присоединяется к корню структуры меньшго размера). Данная оптимизация служит для исключения подобных ситуаций и вводит новое правило: структура большего размера не может быть присоедина к структуре меньшего размера.

Для отслеживания размера структур определяется массив size[], элементы которого в конструкторе инициализируются единицами (так как исходные множества являются одноэлементными):

DSU(int n) {
    for (int i = 0; i < n; i++) {
        id.push_back(i); //id[i] == i
        size.push_back(1); //size[i] == 1
    }
}

Код операции merge() изменяется соответствующим образом: решение о том, какая из структур будет присоединена к другой, осуществяется на основании сравнения их размеров. Размер результирующей структуры соответствующим образом увеличивается на количество присоединённых элементов:

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry)
        return;
    if (size[rx] < size[ry]) {
        id[rx] = ry;
        size[ry] += size[rx];
    } else {
        id[ry] = rx;
        size[rx] += size[ry];
    }
}

После данной оптимизации высота дерева увеличивается на 1 только в результате слияния двух множеств равного размера. Так как таких слияний для N элементов может произойти не более log₂N, высота дерева в худшем случае оптимизируется до logN.

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

Эвристика сжатия путей

Сжатие путей при выполнении операции find

Дополнительно уменьшить высоту дерева можно, если в операции find() перенаправлять все посещённые вершины непосредственно на найденный корень:

int find(int x) {
    if (id[x] == x)
        return x;
    return id[x] = find(id[x]);
}

Данная оптимизация вкупе с предыдущей делает дерево практически плоским, что обеспечивает асимптотику операций, почти равную O(1).

---

Ниже приведён полный код оптимальной реализации системы непересекающихся множеств.

class DSU {

    vector<int> id;
    vector<int> size;

public:

    DSU(int n) {
        for (int i = 0; i < n; i++) {
            id.push_back(i);
            size.push_back(1);
        }
    }

    int find(int x) {
        if (id[x] == x)
            return x;
        return id[x] = find(id[x]);
    }

    void merge(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry)
            return;
        if (size[rx] < size[ry]) {
            id[rx] = ry;
            size[ry] += size[rx];
        } else {
            id[ry] = rx;
            size[ry] += size[rx];
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

};

Некоторые вопросы для размышления:

• Каким образом реализуется операция makeSet(), добавляющая в систему новое одноэлементное множество?
• Как реализовать эвристику объединения по рангу, использующую в качестве критерия высоту древовидных структур?
• Обратите внимание: после выполнения метода find(), использующего эвристику сжатия путей, некоторые элементы массива size[] могут содержать неверную (неактуальную) информацию. Влияет ли это на правильность объединения по рангу? Нужно ли исправлять это несоответствие?

Задачи, рашаемые с помощью системы непересекающихся множеств

Большинство задач, связанных с системой непересекающихся множеств, относятся к так называемым оффлайн-задачам, когда все запросы и их порядок известны заранее. В этом случае допустимо считать и проанализировать все запросы, а также получать ответы на них в порядке, отличном от порядка поступления запросов.

• Расчёт различных функций (сумма элементов, максимум и т. п.) на множествах. Достаточно определить отдельные массивы для значений данных функций аналогично массиву size[], должным образом инициализировать их элементы и обновлять их при слиянии множеств;
• Задача о разрезании графа (запросы об удалении рёбер и принадлежности вершин одной компоненте связности) в оффлайн. Можно считать запросы и выполнять их в обратном порядке (что будет аналогично добавлению рёбер). Полученная задача аналогична тем, которые приведены во введении к данной статье.
• Определение минимального остовного дерева в оффлайн алгоритмом Крускала;
• Определение ближайшего общего предка в оффлайн алгоритмом Тарьяна.

Ссылки

Теория:

• Codeforces EDU — Система непересекающихся множеств
• e-maxx.ru — Система непересекающихся множеств
• neerc.ifmo.ru/wiki — Система непересекающихся множеств
• Brestprog — Система непересекающихся множеств (DSU)
• habrahabr.ru — Система непересекающихся множеств и её применения
• cppalgo.blogspot.ru — Система непересекающихся множеств
• algs4.cs.princeton.edu/lectures — 1.5 Union Find (slides)

Код:

• CodeLibrary — Disjoint-set data structure
• algs4.cs.princeton.edu/code — quick find, quick union, weighted quick union, union-by-rank with path halving

Задачи:

• informatics.mccme.ru — Курс «Структуры данных» — часть 7
• Задачи: Система непересекающихся множеств