74
правки
Изменения
Нет описания правки
На рисунке разные цвета-разные классы,а белые вершины ещё не просмотренные в dfs.
Классы этих вершин - не пересекаются,а значит мы их можем эффективно обрабатывать с помощью <tex>dsu</tex>.
Будем поддерживать массив <tex>ancestor[v]</tex> - представитель множества в котором содержится вершина <tex>v</tex>.
Для каждого класса мы образуем множество, и представителя этого множества.
Когда мы приходим в новую вершину <tex>v </tex> мы должны добавить её в новый класс (<tex>ancestor[v] = v</tex>),а когда просмотрим всё поддерево какого-то ребёнка, мы должны объеденить это поддерево с нашим классом (операция union), и не забыть установить представителя как вершину v (взависимости от реализации это может быть какая-то другая вершина).
Зафиксируем вершины v, и выделим путь от корня до этой вершины. Теперь все рёбра "левее" этого пути уже добавлены в dsu, все рёбра правее — ещё не обработаны, а все рёбра на пути — обработаны, но в dsu ещё не добавлены, так как в dsu мы добавляем при выходе.
