Всем привет, у клавиатуры Кодер Арсений. Проходя одно из соревнований, мне попалась задача, в ходе решения которой я узнал о DSU. Эта вещь очень сильно помогает при решении задач, поэтому я решил изучить её поподробнее.
Теория
DSU - это структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества.
У этой структуры данных есть 3 функции:
- make_set(x) - создаёт для x новое подмножество и назначает этот же элемент представителем созданного подмножества.
- union(x, y) - объединяет подмножества x и y, создавая новое подмножество, представителем которого становится x
- find_dsu(x) - определяет, в каком подмножестве находится x и возвращает его представителя.
Чтобы реализовать подобную структуру наиболее эффективно, нам нужны деревья.
Реализация
Функция make_set(x) реализовывается максимально просто.
Функция find_dsu(x) реализовывается уже тяжелее. Тут мы применим первую эвристику DSU - сжатие путей. После того, как представитель таки будет найден, мы для каждой вершины по пути от X к корню изменим предка на этого самого представителя. То есть фактически переподвесим все эти вершины вместо длинной ветви непосредственно к корню.
Функция union(x, y) требует второй эвристики. Мы просто выбираем случайное ребро для подвешивания (можно и рассчитать, но для этого придётся создавать дополнительный массив, который будет лишней тратой памяти. В большинстве случаев и этого достаточно).
Далее приведены реализации DSU на Python и C++
На этом всё.