DSU: объединяем множества и сжимаем путь

Интерактивный разбор: https://grundyjs.ru/algorithms/dsu/?utm_source=rutube&utm_medium=social&utm_campaign=dsu&utm_content=horizontal Как быстро узнать, входят ли два элемента в одно множество? Система непересекающихся множеств (DSU, Union-Find) хранит группы как лес родительских ссылок. У каждой группы есть корень — представитель множества. find находит этот корень, union объединяет две группы, same сравнивает их представителей. На четырёх элементах A, B, C, D создаём две группы, затем объединяем их по размеру. При равных размерах сохраняем корень A. Первый поиск из D проходит D → C → A; сжатие пути заменяет ссылку D → C на D → A. Повторный поиск делает один переход. Состав множества и размер корня не меняются. B и D уже в одной группе: повторное объединение не увеличивает размер и не уменьшает число множеств. Так Краскал проверяет, не создаёт ли очередное ребро цикл. Обычная DSU умеет объединять множества, но не разделять их. Стрелки parent — внутренние ссылки DSU, а не рёбра исходного графа. В интерактивном примере можно менять число элементов и команды find, union, same, проходить шаги, делиться ссылкой и сохранять анимацию. Сравнение двух и одного перехода относится к показанному пути; это не замер времени и не гарантия одного перехода для любой операции. Авторская озвучка, без музыки. #алгоритмы #DSU #UnionFind #структурыданных #программирование