Сигнал задачи
Когда применять
Связность меняется только объединениями.
Что держать в голове
- Уметь реализовывать find с сжатием пути.
- Уметь объединять по размеру и понимать ограничение структуры.
Сложность
- Сжатие путей и объединение по рангу дают амортизированное O(α(n)) на find/union; память O(n).
Границы и ошибки
- DSU поддерживает объединения, но не обычные удаления рёбер и не хранит сам путь между вершинами.