Hopcroft-Karp法
(graph/hopcroft_karp.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

二部グラフの最大マッチングを Hopcroft-Karp 法で求める。 左頂点数を L、右頂点数を R、辺数を M とすると計算量は $O(M sqrt(L + R))$。

できること

• HopcroftKarp hk(l, r) 左 l 頂点、右 r 頂点の二部グラフを作る
• void add_edge(int a, int b) 左 a と右 b の間に辺を追加する
• int max_matching() 最大マッチング数を返す
• vector<pair<int, int>> get_pairs() 現在のマッチングを (左, 右) の列で返す

使い方

辺をすべて追加してから max_matching() を呼ぶ。 マッチ先は match_left と match_right に入り、必要なら get_pairs() で列挙できる。

実装上の補足

左側だけに BFS/DFS の層グラフを持つ標準的な Hopcroft-Karp 法。

Verified with

• test/yosupo_bipartitematching_hopcroft_karp.test.cpp

Code

class HopcroftKarp {
    int l, r;
    vector<vector<int>> g;
    vector<int> dist;

public:
    vector<int> match_left, match_right;

    explicit HopcroftKarp(int l, int r) : l(l), r(r), g(l), dist(l), match_left(l, -1), match_right(r, -1) {}

    void add_edge(int a, int b) {
        g[a].push_back(b);
    }

    bool bfs() {
        queue<int> q;
        fill(dist.begin(), dist.end(), -1);
        for (int i = 0; i < l; ++i) {
            if (match_left[i] != -1) continue;
            dist[i] = 0;
            q.push(i);
        }
        bool found = false;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int to : g[v]) {
                int u = match_right[to];
                if (u == -1) {
                    found = true;
                    continue;
                }
                if (dist[u] != -1) continue;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
        return found;
    }

    bool dfs(int v) {
        for (int to : g[v]) {
            int u = match_right[to];
            if (u != -1 && (dist[u] != dist[v] + 1 || !dfs(u))) continue;
            match_left[v] = to;
            match_right[to] = v;
            return true;
        }
        dist[v] = -1;
        return false;
    }

    int max_matching() {
        int ret = 0;
        while (bfs()) {
            for (int i = 0; i < l; ++i) {
                if (match_left[i] == -1 && dfs(i)) ++ret;
            }
        }
        return ret;
    }

    vector<pair<int, int>> get_pairs() const {
        vector<pair<int, int>> ret;
        for (int i = 0; i < l; ++i) {
            if (match_left[i] != -1) ret.emplace_back(i, match_left[i]);
        }
        return ret;
    }
};

/**
 * @brief Hopcroft-Karp法
 */

#line 1 "graph/hopcroft_karp.cpp"
class HopcroftKarp {
    int l, r;
    vector<vector<int>> g;
    vector<int> dist;

public:
    vector<int> match_left, match_right;

    explicit HopcroftKarp(int l, int r) : l(l), r(r), g(l), dist(l), match_left(l, -1), match_right(r, -1) {}

    void add_edge(int a, int b) {
        g[a].push_back(b);
    }

    bool bfs() {
        queue<int> q;
        fill(dist.begin(), dist.end(), -1);
        for (int i = 0; i < l; ++i) {
            if (match_left[i] != -1) continue;
            dist[i] = 0;
            q.push(i);
        }
        bool found = false;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int to : g[v]) {
                int u = match_right[to];
                if (u == -1) {
                    found = true;
                    continue;
                }
                if (dist[u] != -1) continue;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
        return found;
    }

    bool dfs(int v) {
        for (int to : g[v]) {
            int u = match_right[to];
            if (u != -1 && (dist[u] != dist[v] + 1 || !dfs(u))) continue;
            match_left[v] = to;
            match_right[to] = v;
            return true;
        }
        dist[v] = -1;
        return false;
    }

    int max_matching() {
        int ret = 0;
        while (bfs()) {
            for (int i = 0; i < l; ++i) {
                if (match_left[i] == -1 && dfs(i)) ++ret;
            }
        }
        return ret;
    }

    vector<pair<int, int>> get_pairs() const {
        vector<pair<int, int>> ret;
        for (int i = 0; i < l; ++i) {
            if (match_left[i] != -1) ret.emplace_back(i, match_left[i]);
        }
        return ret;
    }
};

/**
 * @brief Hopcroft-Karp法
 */

Back to top page