Изменения
Нет описания правки
В любой момент времени текущим паросочетанием будет множество ребер, направленных из <tex>R</tex> в <tex>L</tex>. Корректность работы алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]] и доказанной выше теоремы.
==Псевдокод==
bool '''dfs'''(x):
vis[x] = true
'''for''' <tex>xy \in E</tex>:
k = py[y]
'''if''' (k == -1) or (('''not''' vis[k]) '''and''' ('''dfs'''(k))):
py[y] = u
return true
return false
Kuhn():
py[] = -1
'''for''' <tex>s \in L</tex>:
vis[] = false
'''dfs'''(s)
