Bipartite Matching
(src/graph/BipartiteMatching.hpp)

• View this file on GitHub
• Last update: 2023-04-23 18:55:45+09:00
• Include: #include "src/graph/BipartiteMatching.hpp"

概要

2部グラフにおける最大マッチング，最小点被覆，最大独立集合，最小辺被覆を求める．

• 最大マッチング：どの2辺も端点を共有しないような辺集合．
• 最小点被覆：各辺の端点のうち少なくとも一方を必ず含むような点集合．
• 最大独立集合：どの2頂点も辺で結ばれていないような点集合．
• 最小辺被覆：各頂点を端点にもつ辺を必ず含むような辺集合．

一般に，点被覆の補集合は独立集合をなし，その逆も成立する． よって，最小点被覆の補集合が最大安定集合となり，その逆も成り立つ．

また，最大マッチングの辺集合に対して，マッチングの端点になっていないような各頂点を端点にもつような辺を Greedy に追加していくと最小辺被覆になる．

ここで，2 部グラフにおいては最大マッチングの大きさと最小点被覆の大きさが等しくなる．また，最大マッチングを構築する際の残余グラフから最小点被覆を実際に構成でき，他についても構成可能となる．

よって，それぞれの大きさは頂点集合の大きさを $|V|$，最大マッチングの大きさを $|M|$ とすると，最小点被覆の大きさは $|M|$，最大独立集合の大きさは $|V| - |M|$，最小辺被覆の大きさは $|V| - |M|$ (ただし，孤立点が存在する場合は辺被覆は存在しない)となる．

実装は Kuhn の $O(VE)$ のアルゴリズムを改善したもので，実用上は十分高速で Hopcroft-Karp にも勝ることが多い． これでも間に合わない際には shuffle() をするか大人しく他のライブラリに頼る．

TODO

最小点被覆、最大独立集合、最小辺被覆の実装

Links

• 二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！ - Qiita
• 二部グラフの最小点被覆と最大安定集合と最小辺被覆の求め方
• 2部グラフにおける最大マッチングの個数と最小点被覆の個数の一致 - komiyamの日記
• Паросочетание. Быстрый Кун. - Codeforces
• 二部マッチングでTLEに苦しんだ話 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

Verified with

• test/yosupo/bipartitematching.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <queue>
#include <random>
#include <utility>
#include <vector>

struct BipartiteMatching {
    int U, V, t;
    bool solved;
    std::vector<std::vector<int>> G;
    std::vector<int> L, R, visited;

    BipartiteMatching(int U, int V) : U(U), V(V), t(0), solved(false), G(U), L(U, -1), R(V, -1), visited(U, -1) {}

    void add_edge(int u, int v) {
        assert(0 <= u && u < U);
        assert(0 <= v && v < V);
        G[u].emplace_back(v);
    }

    void shuffle() {
        static std::mt19937 mt;
        for (auto& v : G) std::shuffle(v.begin(), v.end(), mt);
    }

    int solve() {
        for (bool updated = true; std::exchange(updated, false); t++) {
            for (int i = 0; i < U; i++) {
                if (L[i] == -1) {
                    updated |= dfs(i);
                }
            }
        }
        solved = true;
        return U - std::count(L.begin(), L.end(), -1);
    }

    std::vector<std::pair<int, int>> max_matching() const {
        assert(solved);
        std::vector<std::pair<int, int>> res;
        for (int i = 0; i < U; i++) {
            if (~L[i]) {
                res.emplace_back(i, L[i]);
            }
        }
        return res;
    }

private:
    bool dfs(int u) {
        if (std::exchange(visited[u], t) == t) return false;
        for (int& v : G[u]) {
            if (R[v] == -1) {
                L[u] = v, R[v] = u;
                return true;
            }
        }
        for (int& v : G[u]) {
            if (dfs(R[v])) {
                L[u] = v, R[v] = u;
                return true;
            }
        }
        return false;
    }
};

#line 2 "src/graph/BipartiteMatching.hpp"
#include <algorithm>
#include <cassert>
#include <queue>
#include <random>
#include <utility>
#include <vector>

struct BipartiteMatching {
    int U, V, t;
    bool solved;
    std::vector<std::vector<int>> G;
    std::vector<int> L, R, visited;

    BipartiteMatching(int U, int V) : U(U), V(V), t(0), solved(false), G(U), L(U, -1), R(V, -1), visited(U, -1) {}

    void add_edge(int u, int v) {
        assert(0 <= u && u < U);
        assert(0 <= v && v < V);
        G[u].emplace_back(v);
    }

    void shuffle() {
        static std::mt19937 mt;
        for (auto& v : G) std::shuffle(v.begin(), v.end(), mt);
    }

    int solve() {
        for (bool updated = true; std::exchange(updated, false); t++) {
            for (int i = 0; i < U; i++) {
                if (L[i] == -1) {
                    updated |= dfs(i);
                }
            }
        }
        solved = true;
        return U - std::count(L.begin(), L.end(), -1);
    }

    std::vector<std::pair<int, int>> max_matching() const {
        assert(solved);
        std::vector<std::pair<int, int>> res;
        for (int i = 0; i < U; i++) {
            if (~L[i]) {
                res.emplace_back(i, L[i]);
            }
        }
        return res;
    }

private:
    bool dfs(int u) {
        if (std::exchange(visited[u], t) == t) return false;
        for (int& v : G[u]) {
            if (R[v] == -1) {
                L[u] = v, R[v] = u;
                return true;
            }
        }
        for (int& v : G[u]) {
            if (dfs(R[v])) {
                L[u] = v, R[v] = u;
                return true;
            }
        }
        return false;
    }
};

Back to top page