Алгоритм Куна

vector<vector<int>> g;
vector<int> pairFromA;
vector<int> visited;

bool dfs(int vFromA) {
    visited[vFromA] = 1;
    for (int vFromB : g[vFromA]) {
        int &to = pairFromA[vFromB];
        if (to == -1 || !visited[to] && dfs(to)) {
            to = vFromA;
            return 1;
        }
    }
    return 0;
}

void kuhn(int aSize, int bSize) {
    pairFromA.assign(bSize, -1);
    for (int vFromA = 0; vFromA < aSize; vFromA++) {
        visited.assign(aSize, 0);
        dfs(vFromA);
    }
}

Ссылки

Теория:

• e-maxx.ru — Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе
• neerc.ifmo.ru/wiki — Алгоритм Куна для поиска максимального паросочетания
• algorithmica.org — Паросочетания
• Codeforces — Паросочетание. Быстрый Кун
• Brilliant.org — Matching Algorithms

Код:

• codelibrary/cpp/graphs/matchings/max_bipartite_matching_EV.cpp
• algos/Graphs/BipartiteMatchingKuhn.cpp