DSU на Python: как решать + 3 задачи с проверкой

DSU (Disjoint Set Union), он же «система непересекающихся множеств» или union-find — приём для задач, где элементы постепенно объединяются в группы, а вас просят быстро отвечать на вопросы про эти группы. Типичные сюжеты: строят тоннели/дороги и спрашивают «можно ли доехать», люди добавляют дружбы и спрашивают «в одном ли круге», игроки вступают в гильдии и нужен размер объединения.

Как распознать DSU по условию

• Есть операции вида «добавить связь/объединить два объекта».
• Есть запросы «находятся ли A и B в одной группе (компоненте связности)».
• Часто просят «размер группы», «количество компонент», «самая большая группа».
• Важно: связи обычно только добавляются, без удаления (динамическая связность с добавлениями).

Суть приёма: мы храним для каждого элемента «родителя» и представителя группы (корень). Операция find находит корень, а union склеивает два корня. За счёт «сжатия путей» (после поиска сразу переподвешиваем вершины к корню) и «объединения по размеру/рангу» почти каждый запрос работает за время, близкое к константе, даже на десятках тысяч операций.

С чего начать учиться

• Понять две операции: find и union, что такое «корень».
• Добавить эвристики: сжатие путей и объединение по размеру.
• Научиться хранить size[корень], чтобы отвечать про размеры компонент.
• Тренироваться на задачах «строим связи + спрашиваем связность/размер» и аккуратно обрабатывать нумерацию 1..n.

Ниже — задачи с автопроверкой и разбором подхода на DSU.