Вопрос 14 из 31

Практика: графы и маршруты

Как система непересекающихся множеств поддерживает компоненты связности

От чтения к действию

А теперь — вы

Было шесть отдельных объектов. Объединили 1 с 2, затем 2 с 3, затем снова 1 с 3. Сколько компонент осталось?

Разберёмся в теме

Система непересекающихся множеств, или DSU, хранит разбиение объектов на группы. Find находит представителя группы, union объединяет две группы. Для постепенно добавляемых неориентированных связей это позволяет проверять, соединены ли два объекта какой-нибудь цепочкой.

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

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