52
правки
Изменения
→Алгоритм вырезания соцветий
Разобьем каждое неориентированное ребро <tex>(w, v)</tex> на два ориентированных ребра <tex>(w, v)</tex> и <tex>(v, w)</tex>.
Каждое ребро может принимать одно из трех состояний: непосещенное, четное и нечетное.
Для каждой вершины из паросочетания <tex>v</tex> в <tex>mate(v)</tex> будем хранить вершину, смежную <tex>v</tex>.Также для каждой вершины <tex>v</tex> алгоритм в <tex>p(v)</tex> будет хранить родителя в дереве обхода. Сначала проинициализируем все вершины из паросочетания непосещенными, все остальные - четными.
