Изменения

==РелизацияРеализация==

: * Граф <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'''('''int ''' v) { '''if ''' (used[v]) return false;

'''for (int i = 0; i < g[v].size(); i++) { int ''' to = '''in''' g[v][i];:

{ matching[to] = v; '''return ''' true; } } '''return ''' false; } Как вызывать:  int mainfill() { ... чтение графа ... matching.assign (k, -1); '''for (int ''' u = 0; u < n; u++)'''in''' N: { fill(used.assign(n, false); '''dfs'''(u); } for (int i = 0; i < k; i++) if (matching[i] != -1) ... вывод ... }*/