Изменения

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