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

bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) {
    visited[vFromA] = 1;

    for (int vFromB : graphA[vFromA]) {
        int &toFromA = pairFromA[vFromB];

        if (toFromA == -1 || !visited[toFromA] && dfs(graphA, toFromA, visited, pairFromA)) {
            toFromA = vFromA;
            return 1;
        }
    }

    return 0;
}

vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> pairFromA(vertexCountB, -1);

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        vector<int> visited(graphA.size());
        dfs(graphA, vFromA, visited, pairFromA);
    }

    return pairFromA;
}

vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> pairFromA(vertexCountB, -1), greedyVisited(graphA.size());

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        for (int vFromB : graphA[vFromA]) {
            if (pairFromA[vFromB] == -1) {
                pairFromA[vFromB] = vFromA;
                greedyVisited[vFromA] = 1;
                break;
            }
        }
    }

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        if (!greedyVisited[vFromA]) {
            vector<int> visited(graphA.size());
            dfs(graphA, vFromA, visited, pairFromA);
        }
    }

    return pairFromA;
}

Ссылки

Теория:

• 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