25
правок
Изменения
→Реализация: закончил редактирование кода
* Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>
* Функция <tex>dfs(v)</tex> {{---}} обход в глубину, возвращает <tex>true</tex> , если есть увеличивающая цепь из вершины <tex>v</tex>.
* В массиве <tex>matching</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, matching[i])</tex>.
'''bool''' '''dfs'''(v: '''int''' v) : '''if''' (used[v]): '''return ''' '''false''' used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 || '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''' true ''' '''return''' ''' false'''
'''function''' '''main'''(): '''fill'''(matching, -1) '''for''' u v '''in''' NV: fill(used, false) '''dfs'''(uv) '''for (int i = 0; i < k; i++)''' v '''in''' V: '''if ''' (matching[iv] != -1): ... вывод ...*/ '''print'''(v, " ", matching[v])
==Время работы==
