Изменения

Когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений, то есть будем восстанавливать граф (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешим разрешимо за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.