80
правок
Изменения
→Псевдокод
==Псевдокод==
В массиве <tex>px</tex> хранятся вершины <tex>y \in R</tex>, инцидентные <tex>x_i \in L</tex> в текущем паросочетании, для <tex>py</tex> аналогично.
Максимальное паросочетание - такие ребра <tex>(x, y)</tex>, что <tex>x \in L, y \in R, px[x] == y</tex>.
bool '''dfs'''(x)
'''if''' vis[x]
px[x] = y
return true
'''else''' if dfs(py[y]) py[y] = x px[x] = y return true
return false
px[] = -1
py[] = -1
is_path = true; '''while''' (changedis_path) changed is_path = false
vis[] = false
'''for''' <tex>x \in L</tex>
'''if''' (px[x] == -1)
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о паросочетании]]
